你所热爱的就是你的生活 ll
题面
给定一个序列 $price$ , 从序列内任取若干个数 , 使得价值和不超过 $m$ . 求方案总数 .
解题思路
折半搜索 , $l$ 和 $r$ 分别统计左右价值 , 去掉不满足条件的即可 .
家人 Family
题面
在一个 $2 \times n$ 的迷宫中有 2 种状态 , 能走和不能走 . 求给定两点 $u$ , $v$ 的最短路 .
解题思路
线段树维护 $[l , r]$ 列的 $2 \times (r - l + 1)$ 的左上到右上 / 下 , 左下到右上 / 下的最短路的值 .
对两个节点的答案合并 , 经过 $(0 , mid)$ 和 $(1 , mid)$ 的 $\min$ .