因为有四年所以有四个题字。
都是博主的个人想法，不保证做法简洁。
NOI 2017
整数
模拟。
发现要快速进退位，于是用个线段树维护区间是不是全 1 或者全 0，然后二分。
发现二分可以在线段树里面，所以直接线段树上二分。
发现一个线段树节点只维护一位效率太低，于是直接压位。
复杂度 \(O(n\log\frac{30n}{\omega})\)。
蚯蚓排队
模拟。
只看修改直接暴力的复杂度就是对的，因为均摊 \(nk\) 个串每个串长度 \(O(k)\)，而 2 操作会增加最多 \(k^2\) 个长度为 \(O(k)\) 的串，而 2 操作只有 \(10^3\) 个。
考虑怎么查询。愚蠢的博主看到收尾加删就直接上 SAM 了，殊不知直接哈希就可以了。查询复杂度是 \(O(|S|)\) 的。
泳池
求限制下边界的极大子矩形直接上笛卡尔树即可。
直接设 \(f_{i,x,0/1}\) 表示长度为 \(i\) 的区间，下边界都不是危险的，高度最小值为 \(x\)，大小达没达到 \(k\) 的方案数。转移的时候枚举最大值的位置，然后对 \(x\) 后缀和即可。卡下 \(x\) 的上界复杂度就是调和级数，\(O(k^2\ln k)\)。
然后把每个 \(f\) 后面绑上一个下边界是危险的格子对 \(n\) 跑 DP，设 \(dp_{i,0/1}\) 表示考虑前 \(i\) 列，当前大小达没达到 \(k\) 的方案数。枚举最后一段的大小即可。
\(K\leq 1000\) 显然不能矩阵快速幂，考虑常系数齐次线性递推，不用 NTT 直接暴力多项式即可。复杂度 \(O(k^2\log n)\)。
游戏
如果没有 x 直接大力 2-SAT。
有 x 就枚举一下 x 到底取什么。
暴力一点就 \(3^k\)，实测可过，但实际上只需要枚举 \(2^k\) 就可以包含所有可能状态。
复杂度 \(O(2^k(2n+2m))\)。
蔬菜
正难则反。以退为进。
把退菜变成进菜问题就容易很多。直接整个俩堆即可，一个放 \(x=0\) 的，一个放每天都在进菜且菜的 \(x>1\) 的。前者用一个少一个，所以直接取出前 \(m\) 个来。后者取出前 \(m\) 个来后，因为每个菜在这一天至少进一个，所以也至少有 \(m\) 个，在这 \(2m\) 大的里面选 \(m\) 大的即可。
这样还是暴力了点，因为询问太多了。
不能发现第 \(k\) 天的答案必然包含第 \(k-1\) 天的。因为第 \(k\) 天能用的菜第 \(k-1\) 天也能用。所以从第 \(k\) 天推到第 \(k-1\) 天直接删掉 \(m\) 个菜即可。
复杂度 \(O(nm\log n)\)。
分身术
毒瘤计算几何。暴力水 \(20\) 分得了。
对于 \(K=1\)，直接预处理。凸包上第 \(x\) 个点删掉之后，只有极角序在凸包上第 \(x-1\) 到 \(x+1\) 个点之间的点可能会在凸包上。每个点只会被扫两次，复杂度正确。
懒得复读题解。
总结
考察算法全面，类型新颖，部分分足，区分度高，不失为一套好 NOI 题。
正经的总结懒得写。
NOI 2018
归程
Kruskal 重构树 + Dijkstra 最短路 + 树上倍增。
懂的都懂。
冒泡排序
把所有 \(p_i> i\) 和 \(p_i\leq i\) 的拿出来形成两个序列，这两个序列必须都是单调递增的。
考虑 DP 前者，后者直接把剩下的数 sort 即可。
设 \(f_{i,j}\) 表示考虑前 \(i\) 个数，前缀最大值为 \(j\) 的方案数。如果当前点不放数，就 \(f_{i,j}\leftarrow f_{i-1,j}\)，否则当前点放 \(j\)，那么就有 \(f_{i,j}\leftarrow f_{i-1,k}(k<j)\)。
对于求答案，类似数位 DP，强制一个前缀等于 \(q\)，接下来的那一位强制大于 \(q\)，注意到这里需要强制字典序大小，所以需要用到容斥，即 \(p_i>i\) 的序列个数减去 \(p_i>i\) 的序列中不包含 \(i\) 的序列个数。这里可以直接调用 DP 值。
考虑优化 DP。其中 \(f_{i,j}\) 相当于是把 \(j\sim n\) 填到 \(i\sim n\) 中，一个位置要么不放要么 \(p_i\leq i\) 的方案数。考虑把空位全部归给后面的数，在 \(n+1\) 放一个标志符。这样就相当于每个数要分配一个数 \(x\)，其中 \(x=0\) 表示不放，\(x>0\) 表示占用 \(x\) 个位置，且在第 \(x\) 位上放这个数。投影到平面直角坐标系上就是从 \((j,i)\) 走到 \((n+1,n)\) 不能越过 \(y=x+1\) 的方案数，这是经典容斥。
你的名字
大力 SAM 加线段树合并。
求解过程就是先对该串建 SAM 去重，每个右端点有一个 \([1,l1]\) 的左端点限制。
然后放在大串的 SAM 上查，每个右端点有一个 \([l2,i]\) 的左端点限制。
然后就可以求出来每个左端点的范围了。
然后直接计算即可。
屠龙勇士
细节比较多的白给 exCRT。
需要特别注意 exCRT 部分的细节实现。
反正就一模板加细节题。
情报中心
测试点 \(1\sim 4\) 白给分。
\(c_i=0\) 有交就行，求出每条边的最长次长链即可。
剩下的差不多得了。
多边形
前 \(20\) 状压 DP 白给分。
考虑 \(K=1\)，不难发现走过的叶子一定是连续的。不然在中间的叶子就被困住了。
所以直接枚举第一个经过的叶子，最后经过的叶子就是它后面的那个叶子，剩下的部分就要求每个子树可以从最小标号的叶子进去，从最大标号的叶子出来且所有点都遍历到。
考虑 DP，设 \(f_{i,0/1,0/1,0/1}\) 表示节点 \(i\) 的子树，\(i\) 号节点有没有被遍历到，\(i\) 号节点有没有属于一个往下走到当前子树最小标号的叶子的路径，\(i\) 号节点有没有属于一个从当前子树最大标号的叶子往上走的路径，大力讨论转移即可。
枚举之后，树就被切成了森林，每个森林 \(f_{root,1,0,0}\) 的乘积就是答案。
\(50\) 差不多了。
总结
考察算法全面，类型新颖，部分分足，区分度高，不失为一套好 NOI 题。
正经的总结懒得写。
NOI 2019
回家路线
之前不小心把这题漏了。
按照时间排序之后 DP。
一脸可以优化的样子。
机器人
区间 DP 显然。
设 \(f_{l,r,x}\) 表示区间 \(l,r\) 且最大值上限为 \(x\) 的方案数。因为题目限制有用的 \(l,r\) 很少。而 \(x\) 可以做前缀和。
可以发现 \(f_{p,p}\) 的前缀和在值域上是一个一次三段分段函数。所以 \(f_{l+1,r}\) 是一个二次五段分段函数，故 \(f_{l,l+1}\) 的前缀和是一个三次分段函数。
所以 \(f_{l,r}\) 是一个 \(r-l+1\) 次分段函数，且段数为 \(O(r-l+1)\) 级别。
维护多项式不好求前缀和以及乘法，但是可以直接维护 \(O(n)\) 个点值，需要求某个具体点的点值的时候直接拉格朗日插值即可。为了方便维护的点值可以连续，插值的复杂度就是 \(O(n\log mod)\)，因为要求逆元。
似乎有效的 \(l,r\) 个数是 \(O(n)\) 级别的，所以总复杂度大约是 \(O(n^3\log mod)\) 的。当然可以预处理逆元降低一些复杂度。
序列
模拟费用流入坑题。
冷静分析不难，细节稍多。
才不会告诉你是博主懒。
弹跳
KD-Tree 优化最短路。
众所周知线段树可以优化一维最短路。
为了让空间不炸，所以用 KD-Tree 优化二维最短路。
时间复杂度 \(O(n\sqrt{n})\)，空间复杂度 \(O(n)\)。
斗主地
期望 DP。
不难发现两堆牌顺序不变，剩下组合的所有情况出现的概率都是相同的。
所以直接大力 DP，40 分有手就行。
考虑优化，打表可以发现一次函数的期望还是一次函数。大胆猜测二次函数的期望还是二次函数。随便写写就过了。
考虑证明。先考虑 \(f(i)=i\)，即 \(f(i)=c+di\)。设新的 \(f\) 为 \(F\)。下面先讨论左半部分，设其大小为 \(L\)。
\[ \begin{aligned} {n\choose L}F(x)&=\sum_{i=1}^L{x-1\choose i-1}{n-x\choose L-i}(c+di)\\ &=c\sum_{i=1}^L{x-1\choose i-1}{n-x\choose L-i}+d\sum_{i=1}^Li{x-1\choose i-1}{n-x\choose L-i}\\ &=c{n-1\choose L-1}+d\sum_{i=1}^L(i-1){x-1\choose i-1}{n-x\choose L-i}+d\sum_{i=1}^L{x-1\choose i-1}{n-x\choose L-i}\\ &=(c+d){n-1\choose L-1}+d\sum_{i=1}^L(x-1){x-2\choose i-2}{n-x\choose L-i}\\ &=(c+d){n-1\choose L-1}+d(x-1){n-2\choose L-2} \end{aligned} \]
可以发现 \(F(x)-F(x-1)\) 是定值。所以 \(F\) 也是一个一次函数。
类似的，应该也可以证明二次函数的性质。
I 君的探险
只会 \(68\)，无了。
前面的 \(20\) 分有手就行。
对于后面的 ABCD，有一个通用的但是没有办法扩展的做法。
考虑二进制分组，这样对每个点可以求出与它连边的点的异或和。
对于 A，每个点度数只有 \(1\) 直接输出。
对于 B，从后往前扫，当前点 \(x\) 的异或和 \(y\) 就是小于它的唯一与它连边的点，然后把 \(y\) 异或和异或上 \(x\)。
对于 C，全部点亮一遍，叶子的状态不会发生改变。然后直接一遍推。
对于 D，考虑一层一层剥叶子。先考虑所有点，如果一个点 \(x\) 和它的异或和 \(y\) 真的有边，且加上这条边之后 \(x\) 已经记录完了，那么 \(x\) 就是叶子。然后就剥完了一层叶子。对于第二层，扫所有点复杂度就假了，但是这一层的叶子一定和上一层的叶子有边，所以就只用考虑那些点。这个过程每个点的贡献都是自己一次，自己的爹一次，复杂度正确。
后面的就不会了，但是前面的 \(68\) 分简洁好想，后面的 \(32\) 分怎么想都想不出来，这 \(32\) 分不要也罢。
总结
考察算法全面，类型新颖，部分分足，区分度高，不失为一套好 NOI 题。
正经的总结懒得写。
NOI 2020
美食家
暴力 DP 有手就行。
矩阵优化显然。
直接矩阵快速幂优化，复杂度三次方不得行。
发现转移都是向量乘矩阵，预处理 \(2^t\) 的矩阵之后，在转移的时候直接平方复杂度的向量乘矩阵即可。
命运
\(O(n^2)\) DP 显然。
考虑线段树合并优化 DP 转移。
线段树下标表示的就是 DP 第二维的下标。
合并的时候 \(f_{now,i}\) 乘的是 \(f_{son,j}(j\leq i)\)，\(f_{son,i}\) 乘的是 \(f_{now,j}(j<i)\)。
在线段树合并的时候，同时下传当前位置左边的 DP 值的和。那么在合并到指定位置的时候，需要乘的系数就已经求出来了。
因为 DP 问题，这个线段树还需要维护区间求和，区间乘，单点赋值等，但都不难写，唯一需要注意的是需要先合并右儿子再合并左儿子，因为左对右有影响。
复杂度 \(O(n\log n)\)。
时代的眼泪
大力四维莫队 \(O(n^{\frac{7}{4}})\) 加上一个人均特殊性质 A 就有 \(52\) 分了。
根号算法爬。
制作菜品
厉害的构造题。
特殊性质有大用。
超现实树
厉害的思维题。
特殊性质有大用。
翻修道路
菜鸡博主不会弦图。
不会弦图的 OIer 大型自闭现场。
爆零得了，不在乎这几分。
总结
考察算法全面，类型新颖，部分分足，区分度高，不失为一套好 NOI 题。
正经的总结懒得写。
不放代码了，不然显得博客又臭又长。