比 DP 的专题像人了一点儿，但又不完全像。
代码不贴了，太长太抽象了。
[arc084_b]Small Multiple
同余最短路板子。
考虑两种操作，乘 10 和加 1 。显然只有加 1 会产生贡献，然后建个边就完了。
[abc216_g]01Sequence
这不是我们 CSP-S2024 T2 第二问的十倍经验之一么？
- 解法一：直接贪心，树状数组优化，公公又式式啊。
- 解法二：差分约束直接做。\(dis_{i}-dis_{i-1} \ge 0\) ， \(dis_{i-1}-dis_{i} \ge -1\) ， \(dis_{r}-dis_{l-1} \ge c_{i}\) ，但是出题人把 SPFA 杀了，反向直接设 0 的个数就可以转换成正权图， dij 做完了。
P2662 [WC2002] 牛场围栏
同余最短路特有的巧思。
- 解法一：背包。可以证明答案上界很小，复杂度是对的。
- 解法二：同余最短路妙妙题。设 \(x\) 为剩余系的模数， \(dis_{i}\) 表示可以凑出的余数为 \(i\) 的最小数字， 那么其余的 \(dis_{i} + kx\)，k为非负整数则全部可以凑出，但 \(dis_{i} - x\) 显然不能。那么答案就是 \(\max_{i=1}^{x-1}{dis_{i} - x }\) 。
P2680 [NOIP 2015 提高组] 运输计划
数据结构魔怔人出场了。
显然答案一定在最长的那条路径上。我们发现答案是：所有经过这条边的给定路径减去边权 和 不经过这条边的最长边 取 \(\max\)。
祭出树剖，然后上一个线段树一个树状数组，直接大力做完了，跑得还不慢。
P4211 [LNOI2014] LCA
差分比较好想可能是。
- 解法一：树剖 + 差分。
- 解法二：
我才不会说我拿 LCT 写的。
P1852 跳跳棋
哦那我感觉出题人出这种人均零分的题很纸张啊😅
首先考虑四种操作：中间分别向两边，两边分别向中间。设当前位置 \(a,b,c\) ， \(d1=b-a\) ， \(d2=c-b\) 。在 \(d1=d2\) 时只有中间向外跳的情况，不相等时由于只能跨越一个棋子所以只有一种向中间跳的情况。 很不显然的是这是树。鬼知道它为什么是树反正它确实是。然后你发现你建不出来。
那发动想象学竞赛的能力你想象一下，发现可以压缩一下，直接压缩，设 \(d1<d2\) 那跳的次数就是 \((d2-1)/d1\) 。然后瞎跳就跳出来了，终态就卡在 \(d1=d2\) 。反正我觉得跳这个东西还不如我直接跳了得了。
CF1005F Berland and the Shortest Paths
终于可做了😥
题面一眼最短路树，然后考虑加非树边，那么要断掉树上一条边，保证前后 \(dis\) 一致即可，统计方案数直接把每个点方案乘算即可。注意 \(size()\) 返回的是 unsigned 类型，直接乘起来会出锅，随便处理一下就行了。
CF507E Breaking Good
这不是纯水？
这题我讲的，太简单不写了😋
CF1981E Turtle and Intersected Segments
巧巧又思思啊🤓
设 \(a_{i} \le a_{j} \le a_{k}\) ，那么实际上我们只用连接相邻两个就够了，连接 \(a_{i} , a_{k}\) 绝对是不优的。
端点排序后 \(set\) 维护前驱后继即可，细节有一点。
[AGC004D] Teleporter
智慧贪心。
在 1 节点连一个自环，那么“恰好”这个条件直接就被消除了。之后我们从树底部向上遍历，如果深度已经大于 \(k\) ,那么直接连到 1 节点，加个特判就行了。代码也是最短的，大概是比较好想。
[AGC016D] XOR Replace
神奇题。
这题又我讲的，太简单不写了😋
好吧其实找出异或的交换性质，只要能想到连通块就做完了。
CF125E MST Company
什么东西啊，不会😡
什么东西啊，好麻烦😡
CF1707C DFS Trees
抽象。
发现最小生成树的边是固定的，直接找出来标记。
懒得写了。
CF1051F The Shortest Statement
最简单的一集。
注意到这个图极其稀疏，直接检出最短路树，非树边最多只有 21 条。考虑两点间最短路只有树上的和经过非树边的。树上距离直接求，经过非树边的路径，我们可以对这 42 个点记录最短路，然后就能直接求了。
最后二者取 \(\min\) 即可。