P3615 如厕计划
发现女的可以插队，所以从后往前考虑。
如果最后剩两个男的显然不行，发现要么一男一女，要么两个女的，所以记男为 $+1$，女为 $-1$，那么要求每一个后缀和都小于 $2$，因为女的插队就往前走了，显然更大（因为我们实际要求在队列的每一个时刻都有如下性质）。
现在考虑移动的问题，由于只要最不满意的同学满意度最小，所以我们可以考虑每次把一个男的移动到队头，这样只会让所有人都加一并且所有后缀和减一。
那么我们发现答案就是最大后缀和减一。
P5665 [CSP-S2019] 划分
发现一个关键性质，由于段的递增性，最后一段越小总代价越小，由此转移方程：
$$
p(i) = \max j \ \{s(i)-s(j) \geq s(j) - s(p(j))\} \\
f(i) = f(p(i)) + (s(i)-s(p(i)))^2
$$
考虑如何求 $p(i)$。
拆条件：$s(i) \geq 2s(j) - s(p(j))$。
维护递增的单调队列即可。
引入回收机制卡空间。
P2300 合并神犇
同划分，找最大点转移。
P1155 [NOIP2008 提高组] 双栈排序
考虑每一个点在哪一个栈里操作。
考虑数对 $i < j < k$，有 $a_k < a_i < a_j$，考虑到字典序问题，那么 $i$，$j$ 不共存。
连边，跑二分图染色（注意字典序问题），然后就出栈入栈模拟操作，注意字典序问题。
P9870 [NOIP2023] 双序列拓展
要求 $f$ 全大于或小于 $g$。
先考虑第一种，第二种同理。考虑双指针，把一对指针的合法性画在二维表格中，我们需要找一条从左上到右下的路径。
首先若 $X_{min} \geq Y_{min}$ 或 $X_{max} \geq Y_{max}$ 那么有一列或一行无法走。
观察到特殊性质。
剩余的情况 $X_{n} < Y_{min}$ 且 $X_{max} < Y_{m}$。那么最后一行和最后一列都可以走。
那么类似于你给出了一个边框，只要走到边框上就可以了，在前面再做一次，子问题。
对于一般情况。
那么我们找到最小值然后分成左上右下两个问题做。
P7962 [NOIP2021] 方差
考虑差分，发现一次操作实际上交换了差分数组的两项。
打表发现它是单谷，设为初始状态模拟退火即可。
也可以 DP，考虑差分从小到大排序，每次加入头或尾，状态记录 $\sum a$，维护 $\sum a^2$ 即可转移，时间复杂度 $O(n^2 \max a)$。
注意到非零的 $a$ 只有 $\max a$ 个，所以时间复杂度 $O(n (\max a)^2)$。
P1081 [NOIP2012 提高组] 开车旅行
预处理前驱后继，倍增处理开到哪，A 开多少，B 开多少即可。
P9120 [春季测试 2023] 密码锁
发现取得很宽，考虑一个贪心，每一次拨圈使得答案最小。
这样的后效性显然不对，但是我们考虑贪心的顺序，如果我们枚举所有的顺序贪心那么一定可以找到，所以我们随机化即可。
P1979 [NOIP2013 提高组] 华容道
考虑移动空白格。首先需要将空白格移动到关键格旁边，BFS 处理。
图论建模，由于空白格始终在关键格旁边，因此可以设在其上下左右为四种状态，四种状态之间按照步数连边 BFS 处理，然后还有空白格和关键格互换，连边。然后跑 DIJ 即可。
P3953 [NOIP2017 提高组] 逛公园
先跑 DIJ，拆点，按照拆点的 DIS 跑 DP，对于同 DIS 拓扑排序。
P5023 [NOIP2018 提高组] 填数游戏
打表找规律
P3959 [NOIP2017 提高组] 宝藏
状压，$f(s,i)$ 表示选择的集合与最大距离，每次选一个集合来更新，他们都与最大距离的点相连（因为不然一定不优），枚举子集，时间复杂度 $O(n^2 3^n)$。
P9871 [NOIP2023] 天天爱打卡
DP，$f(i)$ 表示考虑到 $i$，奖励用扫描线做，花费把贡献拆开，可以线段树。
考虑到关键点 $l$，$r$，加一个离散化。
注意些细节，线段树维护转移点的贡献，把答案保存下来，每一次用前面的来更新，更逻辑化。
P2680 [NOIP2015 提高组] 运输计划
二分答案，显然大于这个答案的路径的并集（树上差分打标记）上的最大边权是要减掉的，检查即可，注意二分边界（卡卡常）。
P1315 [NOIP2011 提高组] 观光公交
先打一个暴力，拆拆式子，贪心即可。
P5021 [NOIP2018 提高组] 赛道修建
树，二分答案，求最多赛道数，检查。对于每一个子树，可以选一条往上给，合法的扔掉，剩下的尽量凑（从小的开始用）。
P7619 [COCI2011-2012#2] RASPORED
拆式子，找到顺序，值域很小，上树状数组。
P3426 [POI2005] SZA-Template
$f(i)$ 为 $i$ 或 $f(fali(i))$。
为 $f(fail(i))$ 当且仅当存在 $f(j) = f(fail(i))$ 使得 $i - fail(i) <= j$。
P6653 [YsOI2020] 造林
找到重心，由于重心的性质，最大子树一定包含重心。换而言之嫁接了一个点之后只会影响 除了 其到重心路径上的所有点。
从重心开始 DFS，我们发现最大子树一定增，这样我们只需要字符串哈希就维护出了这个可重集。
特判重心的最大子树，双重心拆开。
P7320 「PMOI-4」可怜的团主
对于 DFS 生成树，保证根节点度数不为 $1$，叶子之间两两没有边。
若有 $\lfloor \frac{n}{3} \rfloor$ 个叶子，选第二种，否则选第一种。
对于第一种，我们考虑把叶子按照 DFS 序取出来。
前一半和后一半连边。
考虑每一个点，每一个子树中必有一个叶子，所以一定会跨子树连接，或者直接连出去。
如果只有一个子树，那就一定会连出去，否则就是根节点，矛盾。
P7393 「TOCO Round 1」Eternal Star
对于一个点 $i$，他必须有 $1$ 到 $i-1$ 的所有子树，每一个有 $x=i-j+1, i+xj<x(j+1)+j$，递归创建。
这样太大了，考虑直接把两颗 $K-1$ 的子树连接起来，其中一个将变成 $K$，这里下面子树数量要按照 $K$ 的建。
P7124 [Ynoi2008] stcm
DFS序转换成区间问题，分治，当前区间表示所在区间没有被包含。
分治到子区间去做，考虑无法分治的部分。树上区间显然不会相交，所以剩下的一定是一个包含的关系，从两边开始删就可以了。
时间复杂度 $O(n\log n)$。
P8329 [ZJOI2022] 树
跳过(FLG)。