前言
NOIP 前开始做做真题，虽然每年都风格迥异，不过感受一下 OI 风格的题目还是有一定意义的。
P1016 旅行家的预算
贪心地考虑，在一个油站，如果加油，要么加满，要么加到足够行驶到下一个加油点的油量，在下一个更便宜的加油点再加油。
是否存在后效性呢？在下一个油站始终可以加满，所以应该没有。 当然，这鬼数据范围乱搜一下就完事了。
|
|
P2114 [NOI2014]起床困难综合症
拆位考虑，对于每一位，考虑初始为 $0$ 或为 $1$ 时最终会变成什么，然后随便搞搞就行了。
然后一个最高位的贡献超过所有低位，所以贪心从高往低，选零有贡献就选零，否则选一有贡献就选一。
|
|
P2827 蚯蚓
跟今年的贪吃蛇一样的双队列优化。
首先全局加看上去就很假，转化为单点减即可，然后容易想到用 multiset 之类的东西来维护一下最大值，就可以做到带 $\log$ 的解法。
正解要求 $O(m)$，需要发现题目隐藏的单调性。
一个自然的想法是按照被切过的蚯蚓和没切过的进行分类。
假定一开始切了一条长度为 $a$ 的蚯蚓，后来 $t$ 秒后切了一条当时长度为 $b$ 的蚯蚓。
在切完 $b$ 时，其长度分别为 $\lfloor pa \rfloor + t \times q$，$a - \lfloor pa \rfloor + t \times q$，$\lfloor p \times (b + (t-1) \times q)\rfloor$，$b + (t-1) \times q - \lfloor p \times (b + (t-1) \times q)\rfloor$
一开始有 $a>b$：
$$ \lfloor pa \rfloor + t \times q - \lfloor p \times (b + (t-1) \times q)\rfloor $$
$$ \implies \lfloor p \times (a + \dfrac{1}{p} \times t \times q) \rfloor - \lfloor p \times (b + (t-1) \times q)\rfloor $$
$$ \implies \lfloor p \times (a + \dfrac{1}{p} \times t \times q - b - (t-1) \times q)\rfloor $$
$$ \implies \lfloor p \times (a - b + ((\dfrac{1}{p} - 1) \times t + 1)\times q)\rfloor $$
这东西显然是正的，那么先分的左半边会大于后分的左半边。
另一边也是差不多的证明方法。
那么乱搞一下，分成三类：没切过的，切了的左边的，切了的右边的，就可以线性了。 一开始给所有蚯蚓排序，总时间复杂度 $O(n \log n + m)$.
然后数组注意要开很多倍大小，因为要考虑到出队的元素空间依然占用，需要开操作数的两倍。 最后把三个队列归并起来，炫酷拉风的三路归并科技。
|
|
P7078 贪吃蛇
足够聪明的蛇蛇。
首先有一个结论：如果一条蛇吃完不是最弱的，它一定敢吃。
一条蛇吃完后，下一条蛇如果吃，吃完后一定比它弱，而如果下一条蛇吃，就说明下一条蛇吃完不会被吃，那么它比下一条蛇强就更不会被吃。如果下一条蛇不吃，那么游戏结束，它也不会被吃。
效仿蚯蚓，我们来 YY 一下，也许每条吃完的蛇长度都是单调减小的？最弱的越来越大，因为没有蛇吃完会变成最弱，所以最弱单调递增，最强单调递减，最强吃完最弱后也单调递减。
然而此时，你会发现一个问题：最弱不一定单增！因为你足够聪明。
因为如果有一条蛇足够大胆，它会发现下一条蛇不敢吃它，因为下一条蛇吃了就会被吃，所以它敢吃而变成最弱。
这就是单调性被破坏了，此时它敢不敢吃，完全取决于它的下一条蛇敢不敢吃。
它的下一条蛇敢不敢吃呢？如果它吃完不是最弱的，它一定敢吃，否则又要取决于下一条蛇。
这就是个递归，边界在哪里呢？如果只有两条蛇，那么一定敢吃。
这个阶段也是有单调性的，每条蛇吃完都是最弱，顺次模拟下去。
细节恶心死了，居然逼得我又写起了恶心封装。
|
|
P2119 魔法阵
可以考虑先按 $X$ 进行排序，然后依次数数。 又是神奇的数数题啊。
第一种情况，$X_a < X_b < X_c < X_d$，此时 $a = i$.
那么就是要统计 $a < b < c < d$ 中，满足 $X_a = X_b + 2 \times X_c - 2 \times X_d$，且 $X_a > X_b - \dfrac{(X_c - X_b)}{3}$ 的数量。
值域比较小，感觉要从值域上做手脚了。
$X_a > \dfrac{4}{3} \times X_b - X_c$
首先，可以发现，$X_b - X_a = 2 \times (X_d - X_c)$ 这个式子是有意义的，可以考虑为两个值的差两倍于令两个值。并且可以发现，$X_b - X_a$ 是偶数时才合法。
然后其实 $X_b - X_a < \dfrac{X_c - X_b}{3}$ 也是有意义的，限制了 $c$ 点的范围不能太远，再结合值域，感觉就是打个暴力了。
之前的式子应该都全部白化简了。
可以考虑枚举 $X_b$，然后再枚举 $X_a$，保证 $X_b - X_a$ 是偶数，然后 $X_b - X_a = 2 \times (X_d - X_c)$，因此上界是 $10000$，而每次跳两步，其实是 $O(5000^2)$ 的。
此时只需要查询对于所有合法的 $X_c$，差分数组打个标记，然后对每个 $X_c$ 的对应的 $X_d$ 也标记一下，这时候发现一开始枚举差值会比较好。
乱搞一下就行了，反正是普及组的题目。
大概就是枚举差值，然后做个可行对数前缀和，然后再差分做区间修改。细节多，多调调就行了。普及组的假题。
|
|
P2822 组合数问题
小常数的 $O(n^2k)$ 应该是能过的，只要把取模避免掉就可以了，那么直接统计阶乘中对应指数位的数值即可。 做个二位前缀和之类的东西。 空间不够用，那就质因数分解，只有 $2$，$3$，$5$，$7$，$11$，$13$，$17$，$19$ 这么一共 $8$ 个质数，那么空间就够了。
然而答案记录还是要开满，然后一眼突然发现……原来 $k$ 是固定的？我在干啥？
sb 题，直接递推组合数取模即可。
|
|
LOJ 6520. 「ICPC PacNW 2017 Div.1」David 的旅程
突然插入这道题，是为了给回家路线做个小铺垫。
考虑从航班来动态规划，有一个很 naive 的状态设置：设 $f(i,j)$ 为当前时间为 $i$，目前在城市 $j$ 的最小挫败感。
对于每一条航班，都有：
$$ f(e_i,v_i) = \min \limits _{0 \le k \le s_i}f(k,u_i) + (s_i-k)^2 $$
这种形式看上去就很斜率优化，然而这二维的状态实在是优化不起啊。 考虑想办法拆掉一维，既然时间已经在转移方程中出现了，似乎只能想办法拆掉城市了。
每条路径，更新的都是 $v_i$ 城市中的答案，并且只会更新一个点。而对于路径 $u_i \to v_i$，$v_i$ 城市的状态需要从 $u_i$ 城市转移。
这可以看做一个单点更新操作与一个查询操作，把它们拆开考虑。
对于一个路径 $u \to v$，要求 $v_i \le u$ 的所有修改操作都被加入，就能进行转移。然而稍一思考，就会发现，这东西可以成环，没法做啊。
滚回来想办法拆时间，可以发现对于一条路径，它需要考虑的路径只有到达时间小于等于它的出发时间的路径。
因此对路径的出发时间进行排序，然后用双指针的技巧动态插入 $f(t,v_i)$ 这样的修改操作，然后查询一次，又把查询造成的修改扔到待应用队列中。
对每个站点，都可以大力维护一个单调队列，插入会满足时间单调递增，也就是横坐标单调递增，所以这是很自然的。
然后把式子拆开吧：
$$ f(e_i,v_i) = f(k,u_i) + s_i^2 + k^2 - 2 \times s_i \times k $$
整理一下：
$$ 2 \times s_i \times k - s_i^2 + f(e_i,v_i) = f(k,u_i) + k^2 $$
斜率是 $2 \times s_i$，截距是 $f(e_i,v_i) - s_i^2$，横坐标是 $k$，纵坐标是 $f(k,u_i) + k^2$，要求最小化截距。
|
|
P5468 [NOI2019]回家路线
似乎是差不多的做法了，只是贡献统计变了罢了。
$$ f(v,s_i) = f(u,k) + A(s_i - k)^2 + B(s_i - k) + C $$
$$ \implies f(v,s_i) = f(u,k) + A \times s_i^2 + A \times k^2 - 2 \times A \times s_i \times k + B \times s_i - B \times k + C $$
$$ \implies 2 \times A \times s_i \times k + f(v,s_i) - A \times s_i^2 - B \times s_i - C = f(u,k) + A \times k^2 - B \times k $$
观察一下，斜率是 $2 \times A \times s_i$，截距是 $f(v,s_i) - A \times s_i^2 - B \times s_i - C$，横坐标是 $k$，纵坐标是 $f(u,k) + A \times k^2 - B \times k$.
求 $f(v,s_i) = y - k \times x + A \times s_i^2 + B \times s_i + C$
要求最小化截距，可以维护一个斜率单调递增的下凸包。
|
|
P3960 列队
可以发现，每次离队一个人，只会改变一行一列一点。
变化量比较小，所以可能不是找规律。
考虑一个点 $(x,y)$，它目前的编号是什么。这取决于它被如何移动，具体地，它左方的点被删去，它就会被移动。除此之外，第 $m$ 列是很特殊的一列，每次删点都会导致其移动。
考虑一下，用动态开点线段树维护，具体看代码吧。
大概就是维护删了多少个点，然后在树上二分第 $k$ 个点这样的东西，在结尾插入又得重写个判断的鬼东西。这种毕竟还是平衡树做比较正统。
|
|
P1084 疫情控制
树上最大值，考虑二分答案。
转化为检验问题，可以发现一个点往上一定更优，所以无脑让所有点往上跳。
每个支配点都往上跳，在跳到的点把支配点存下来，然后大力搜索一遍检查首都的每个子树是否满足。
对于不满足的子树，必须从别的子树跳过来，可以发现必须是别的子树的根节点才有可能，维护一个 multiset 用于乱跳即可。还有一个点：如果某个跳到 $1$ 的点，剩余的不足以跳回去，那么一定让它不跳，留着支配它的源子树。
|
|
P1081 开车旅行
首先确定每个点移动后到达哪个点，绝对值不好处理，可以用 set 二分判断。
然后倍增一下，处理每个点当前点为 $A,B$ 时跳 $2^i$ 步之后会到哪个点，顺便处理距离。
然后就可以在某个状态下一步到位。
细节比较恶心。代码有很多优化空间。
|
|
P5688 [CSP-SJX2019]散步
毒瘤题？
考虑每个人都会前往最近的出口，花费一定的时间。只需要每次处理最快到达的人，就不会有什么问题。
如何处理？可以发现，如果最快的人离开后，出口仍有容量，则一切不变。如果容量为零，那么该出口相当于被删除。
被删除后，原先最近出口是该出口的人，对应的值都会变化。一个 naive 的想法就是对每个出口储存对应的人的信息，然后暴力修改。
然而这样，一个人的信息被多次修改，复杂度是不可接受的。
可以发现，在位置上，这些最近出口相同的人是连续分布的，可以考虑求出这个区间，然后用数据结构区间修改其花费的时间。
我选择使用线段树维护 $t$ 与 $id$，即每个人前往最近的出口花费的最小时间与对应的最近出口，顺时针逆时针分开建树。
可以用一个链表来维护动态删除出口。
需要讨论绕过原点的情况，恶心，十分恶心，超级恶心。
|
|