$\color{orange}{\texttt{佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚佛脚。}}$
因为曾经AFO多年，导致 S组补题计划咕了两年整。
这并不很有趣嘛。
_注：以下只收录难度绿—紫的真题_
_UPD：如你所见，那道黑题它A了。_
这篇文章主要采用叙述式风格，这会显得极其枯燥，所以看不下去的读者可以看看图找点乐子。
声明：本文中所有引用皆为断章取义，请勿无有端联想！
$2451545 (Julian)$ 前（fixed again）
简易的分类讨论 + 困难的贪心。
每次装到能抵达下一个价格更低的地方为止。然后开过去。
如果装满了也到不了，就在自己这里先把油加满，再开到价格相对最低的地方。
实现很烦。
简易的暴搜 + 改变搜索顺序的 $trick$ 。
搜索很简单，预处理质数表，随缘跑 $dfs$ 。
主要是要求首行首列和最小，可以用 $nxt$ 数组控制“下一个搜的位置”以达到这一效果。
简单思维 + 高精思想。
一行里有几个两位数就代表这是几。
最后需要逐一验证，这里要手打一个高精一样的玩意实现 $K$ 进制。
$2452276(Julian)$ 前
简单搜索 + 毒瘤高精。
预处理把某一位 $i$ 后 $j$ 位数单独分出来是多少。
以搜到第 $pos$ 位，用掉 $k$ 次分割机会为状态，记忆化暴搜。要写高精。表示：
偏板的 $dp$ + 简单的压维优化。
转化为两个人从左上角走向右下角。
设计状态：$dp[i][j][k][l]$ 为第一个人走到 $(i,j)$ ，第二个人走到 $(k,l)$ 的最优解。
转移方程：
因为两人走过的路程必定相等，故可以压掉最后一维。用前三维来算 $l$ 。优化：
初级的建图 + 最短路。
城市与城市连边，火车站之间连边，跑最短路即可。
需要写函数求笛卡尔坐标系上点距。
$2453006(Julian)$ 前
中等搜索。
以“搜到第 $pos$ 个点，覆盖这些点用了 $sum$ 个矩形”为状态 $dfs$ 。
加最优性剪枝，开结构体装矩形，重载运算符，手打函数以实现加点和判交。
$dfs$ 状态不好想。还是题刷少了。
简单图论。
把所有初始状态为 $1$ 的结点入队，跑 $bfs$ 即可。读者：
$2453737(Julian)$ 前
中等 $dp$ 。
设计状态：$dp[i]$ 表示到达 $i$ 点最少需要走几步。
状态转移：$dp[i]=\min\{dp[i-k]\}+1\;(k\in[L,R])$
但是需要路径压缩节省空间，若两点之间距离超过 $R*(R+1)$ 则可以压成一个点。
复杂思维题。
求变动次数，相当于是求不变人数。
不停的转动目标环和当前环，比较匹配个数。
提前处理好 $dis$ ，表示当前环上这个数到目标环上需要转动几次：
困难搜索 + 改变搜索顺序的 $trick$ 。
依次搜索每个字母分别代表什么。
写 $judge$ 函数判断当前情况是否合法。
改变搜索顺序从较低位开搜。
$2454467(Julian)$ 前
简单模拟。
每次找到第一个空位，向后查能不能安排得下这么多。
直到第一个能放下的位置放下即可。证明：
困难组合数学。
推式子，若 $k|n$ 且每一位都不填 $0$ ，那么就是在 $2^k-1$ 个数中安排合适的顺序填，有 $C^{n/k}_{2^k-1}$ 。
若允许填 $0$ ，与上种情况一加，则枚举哪一位开始填的 $0$ ，有 $\sum^{n/k}_{i=2}C^{i}_{2^k-1}$ 。
若 $k\not|n$ ，若首位为 $0$ ，则后面退化成了上面那种情况。
若首位不为 $0$ ，后面全部受前面限制。有 $\sum^{2^{n\bmod k}}_{i=1}C^{n/k}_{2^k-i-1}$ 。
所以总式为：
主要式子难推。
$2455198(Julian)$ 前
简单数学。
有 $\gcd(x,a_0)=a_1$ ， $x*b _ 0/\gcd(x,b_0)=b_1$ 。
故有 $\gcd(x/a_1,a_0/a_1)=1$ ， $\gcd(b_1/x,b_1/b_0)=1$ 。
那么枚举 $b_1$ 的约数，测试是否满足如上条件即可。感想：
中等图论 + 简单 $dp$ 。
两次 $dfs$ 处理出 $1$ 号点可达的点和 $N$ 号点可达的点。
对于每一个 $1$ 号点可达的点 $u$ ，枚举每一条出边，倘若某出边抵达的点 $v$ 可达 $N$ 点，则在 $val_v$ 和 $val_u$ 之间连边（邻接表）。
跑 $floyed$ 传闭包。最终找到互相可达的最大差值的 $val$ ，其差值为答案。
简单暴搜 + 改变搜索顺序的 $trick$ 。
开 $hang,lie,gong$ 等数组表示各自范围内填数情况。
将 $0$ 少的行尽量先算以压缩搜索树。
写函数计算价值。回溯并更新。
二分图染色 + 中等贪心。
用栈的性质推知 $i<j<k$ ， $a_k<a_i<a_j$ 的情况是不可能的，故可因此构建出限制条件连边，二分图染色，分出两个栈来。
维护指针“现在该弹哪一个”，并选用贪心策略：尽量先走 $1$ 栈，尽量先 $push$ 。
实现难。
$2455563(Julian)$ 前
简单 $dp$ 。
开四维数组 $dp[i][j][k][l]$ 表示用了 $i$ 个 $1$ ， $j$ 个 $2$ …… 的最大价值。
从四种情况转移过来即可。
简单搜索 + 中等问题转化 。
先搜索出每个蓄水场能灌溉到最底下一行的哪些位置。
可证各个蓄水场能灌溉的位置必连续。
将题目转化为最小线段覆盖问题即可。
问题转化难想。
$2455928(Julian)$ 前
中等数数。
整前缀和，在 $for$ 循环跑客栈的过程中，实时更新某种颜色出现的次数。
每出现一个客栈，倘若它之前有过 $pre$ 个同颜色的，就使答案增加 $pre$。
注意各变量改值的顺序。
基础前缀和 + 基础二分。
二分这个 $W$ 。
每次 $judge$ 时做前缀和，暴力计算即可。
水蓝。
复杂思维。
预处理每个时间点上车上的人数。可知装一个加速器会让当时在车上的人受益。
每次贪心选受益最大的就是了。选完以后记得重新更新。
正确性可以保证。
$2456294(Julian)$ 前
简单数据结构。
租用一段时间相当于在这些时间 $-1$ 。
如果某个时间点被减到 $0$ 以下，则说明不可行。
敲一棵线段树即可。复杂度：
复杂 $dp$ + 复杂倍增优化。
先配合 $set$ 预处理出在 $i$ 点上，某人（0/1）开车时会去哪。记作 $nxt[i][0/1]$ 。
设计状态 $arr[0/1][i][j]$ 为某人（0/1）从 $i$ 点出发，开车 $2^j$ 次到达的地方，显然有初始化：
设计状态 $dp[0/1][0/1][i][j]$ 为从 $i$ 点出发，某人（第二维0/1）先开车，总开车 $2^j$ 次的过程中，某人（第一维0/1）行驶的路程，显然有初始化：
对于这 $2^k$ 的前半段和后半段是否是同一人开车分类讨论，有：
当 $j=1$ （即前后两段不同人）：
当 $j!=1$ （前后同人）：
这样我们就处理出了所有的开车方法，询问时将 $j$ 从大到小枚举，逐个累加即可。
要求对算法灵活运用：
困难图论。
要最小化用时，就得二分这个时间，重在 $judge$ 函数。
先贪心地尽量把军队往根上移，因为根结点不能驻扎军队，所以如果一支军队可以移到根结点以上，则先把它停在根结点的一个儿子上，并且存一些剩余的时间。
我们称这些儿子为已驻军点。
再从根往下跑 $dfs$ ，求出根结点下属的哪棵子树还未被切断，处理这些子树根结点到全树的根结点的距离。
我们称这些根结点为未驻军点。
贪心地让剩余时间少的已驻军点，移向离根结点距离近的未驻军点。
若未驻军点都可被移到，则可行，尝试更小的时间。
实现十分困难。
$2457024(Julian)$ 前
简单图论。
两点距离为 $2$ ，说明必然只有一个中间点把他们两个连接。
那么 $O(n)$ 枚举一下这个中间点，取 $\max$ /求和即可。
中等 $dp$ + 压维优化。
设置状态 $dp[i][j]$ 表示在二维平面上达到 $(i,j)$ 所需的最小点击次数
。
有转移
$i$ 只与上一位有关，滚掉即可。
摸索到正解要较长时间。形象化：
中等图论。
建反图跑 $dfs$ ，求出能抵达终点的点有哪些，染色。
建正图，跑只通过已染色点的 $dij$ 即可。
刷大量图论以掌握反图的灵活运用。
指刷题量。
简单数学。
枚举 $x$ 取值，用秦九韶算法求值判断即可。
$2457389(Julian)$ 前
复杂搜索。
先搜顺子，数据不大，暴力枚举可能出现的顺子情况，更改状态往下搜（ $dfs1$ ），搜后复原。
同时在 $dfs1$ 中调用 $dfs2$ ，其作用为搜索最少出牌次数，传4个参数，代表单牌张数，对子张数，三个头张数，炸弹张数即可。
$dfs2$ 中除了正常出牌策略外，还可有拆牌选项，即“不消耗出牌次数，将XXX牌型（如：一对）拆成几个XXX（如：两张单）。”
在 $dfs1$ 过程中更新最小值即可。
应学会把不等价操作转为等价。
指题解。
中等 $dp$ + 滚动数组优化。
设置状态： $dp_{i,j,k,l}$ 表示：“决策到原串的第 $i$ 位，匹配串的第 $j$ 位，已用掉 $k$ 次拆分次数，这个第 $i$ 个数是否（1/0）用来匹配”的方案数。
有
滚掉第一维。
应掌握在 $dp$ 数组下标中设置 $0/1$ 维度，对之分类讨论。
代码很短。
中等图论 + 中等二分。
题目要求使最长航线最短，故二分最长航线的长度。
所有超过这个二分出的长度的航线，说明都需要加速，可以用 $LCA$ 求出某条航线长度。
对每一条超过的航线做树上差分，若某一条边差分出来的值 = 超过航线的数目。说明这条边被所有超过的航线经过，故这是一条可以加速的边。
取所有可以加速的边中的最大值来加速，若使所有航线中最长的一条也低于了我们二分出的值，则这是一种可行的方案，尝试更小的长度。
重在思维和马速，细节不多。
$2457754(Julian)$ 前
简单图论 + 中等 $dp$ + 中等概率期望。
结点数少，可 $floyed$ 求两点距离。
设置状态 $dp_{i,j,k}$ 表示决策到第 $i$ 节课，已用掉 $j$ 次申请机会，这节课是否（0/1）申请时，走过路程的期望。
另设 C1 指上节课本该在的教室， C2 指这节课本该在的教室， D1 指上节课换去的教室， D2 指这节课换去的教室。
设 $pr[i]$ 为第 $i$ 节课换成功的概率。
显然有：
码量不大。公式别抄错了。
复杂思维。
手模发现每一次砍的蚯蚓单调递增。
维护三个队列，分别装原蚯蚓，切后较长的蚯蚓，切后较短的蚯蚓 。
每次取三个队列中的队首中最长的一条，取出并根据当前天数修改长度值。切后，将都两段减去一些长度值（表示少成长了这么多天），放入相应队列。如此往复即可。
重在思路的推导，这题看了题解。
中等搜索 + 中等状压 。
跑 $dfs$ ，参数包括：还剩下多少猪要打，决策到第几头猪，已用了多少抛物线。
对于每一只猪，若它被之前的某条抛物线经过，则跳过，搜索下一只猪。
若没有，尝试它可以和哪一只还未打的猪串起来一起打，向下搜索。
用状压记录每一只猪是否被打掉的状态。
不需要用到 $M$ 。
$2458119(Julian)$ 前
中等图论 + 困难 $dp$ 。
建正反两图。在正图上跑 $dij$ ，求出 $1$ 号点到其他点的最短路 $dis$ 。
在反图上跑 $dp$ ，设计状态 $dp[u][k]$ 表示决策到第 $u$ 个点，路径比最短路长 $k$ 的方案。
有：
用记搜实现即可。注意先判环，有 $0$ 环在最短路上则为无限解，可用 $Bellman-Ford$ 解决。
能通过所有 $hack$ 数据。
中等随机化。
生成开发顺序排列，以代价作为 $\text{calc}$ 函数返回值，若更优或一定概率下更劣，则在原序列基础上随机交换两个元素，否则 $\text{random_shuffle}$ 生成新排列。
出正解率极高。
$2458484(Julian)$ 前
简单递推。
设置 $flag$ 数组存三种值： $0$ —— 未能被凑出的面值， $1$ —— 能被凑出的面值 ， $2$ —— 本来就有的面值。
枚举当前所有 $flag$ 非零的面值，筛一下后面的面值（改一些面值对应的 $flag$ 为 $1$ ）。有时可以将一个 $2$ 覆盖成 $1$ ，表示这种初始面值是不需要的。
最后扫一遍 $flag$ 数组，有几个 $2$ 就是需要多少初始面值。
中等图论。
二分最短的赛道长度。以之为标准跑 $dfs$ 获取路径长度。若某条路径长度大于标准，则可行路++，若小于，则丢进 $set$ 等待匹配。
在 $set$ 里用 $\text{lower_bound}$ 尽可能多地拼路径，若可行路径 > $M$ ，则尝试更大的 $mid$ 。
$set$ 改 $multiset$ 也可。
咕咕咕！
最后更新： 2021年04月17日 16:07
原始链接： https://quest233.github.io/2021/04/17/NOIP-%E8%BF%87%E5%BE%80%E7%9C%9F%E9%A2%98%E6%B3%9B%E5%81%9A/