20联赛集训day12 题解
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
A一个暴力的想法是找出这条链，暴力跳。跳的定义是走到第一个满足和 $\geq k$ 的位置。于是可以想到用倍增。设 $f_{x,i}$ 表示 $x$ 点跳 $2^i$ 步在哪个点，首先跳 $2^0$ 步可以二分预处理，然后直接转移就好了。但是这只能处理往上的，往下怎么做呢？一种方法是直接树链剖分，就变成了若干个链的问题，但是这是 $O(\log^2n)$ 的，又难写又难调。我们可以观察到对于...
题目链接题目大意坐标轴上有 $n$ 个点 每个点有一个收益 $v_i$ 。你从 $s$ 点开始 在接下来的 $m$ 天里每一天你可以选择移动到相邻的城市或获得这个城市的收益。一个城市的收益只能被获得一次。求最大可能的收益。$n \leq 10^5$题解发现这个路径只可能是先往左，在折回来往右（或者倒过来）。我们只需要考虑第一种情况（后面那种情况可以通过 reverse 再做一遍得到）如果我们...