ABC 好题
题单介绍
这里存放了 `abc200` 到 `abc225` 中的一些相对好的题，难度适中，码量不大。
正在更新……
下面是一句话做法，没有启发。
---
- [Game in Momotetsu World](https://www.luogu.com.cn/problem/AT_abc201_d)：
伪装成博弈论的 DP，可以用寄搜实现，基于回合奇偶性决定取 $\text{max}$ 还是 $\text{min}$。
- [Xor Distances](https://www.luogu.com.cn/problem/AT_abc201_e)：
求出路径异或和，将异或式分解，按二进制逐位计算贡献，利用异或的性质解决。
- [National Railway](https://www.luogu.com.cn/problem/AT_abc210_d)：
强制确定方向后 DP 两遍，再将矩阵翻转四遍跑四遍 DP。
- [Divide Both](https://www.luogu.com.cn/problem/AT_abc206_e)：
不需要做差分，直接容斥，加上一点点分类讨论，需要线性筛出 $\mu$。
- [Ring MST](https://www.luogu.com.cn/problem/AT_abc210_e)：
标准结论题，与 $\gcd$ 的性质相关，用到了 kruskal 的思想。
- [Pond](https://www.luogu.com.cn/problem/AT_abc203_d)：
二分答案，根据答案大小将矩阵变成 01 矩阵，做前缀和后 check。
- [Mod i](https://www.luogu.com.cn/problem/AT_abc207_e)：
在前缀和数组上 DP，利用同余的性质累加对应的前缀和，$O(1)$ 得出答案。
- [Safety Journey](https://www.luogu.com.cn/problem/AT_abc212_e)：
在反图上 DP，将普通 DP 的累加改为与上一层的和做差。
- [Chain Contestant](https://www.luogu.com.cn/problem/AT_abc215_e)：
在值域很小的字符串上可以进行状压 DP，需要一点点结论。
- [Packing Under Range Regulations](https://www.luogu.com.cn/problem/AT_abc214_e)：
自然的贪心，排序后用堆确定位置。
- [Dist Max 2](https://www.luogu.com.cn/problem/AT_abc215_f)：
二分答案，维护一个大根堆和一个小根堆来帮助 check。
- [Max Sum Counting](https://www.luogu.com.cn/problem/AT_abc216_f)：
将 b 按 a 排序后 DP，需要前缀和优化。
- [Blocked Roads](https://www.luogu.com.cn/problem/AT_abc218_f)：
注意到最短路上的边的数量是 $O(n)$ 的，因此对于每一条在最短路上的边暴力再跑一遍 bfs 是正确的。
- [Sum of Maximum Weights](https://www.luogu.com.cn/problem/AT_abc214_d)：
将边从小到大排序，用并查集维护连通块，将边逐一加入并计算贡献。
- [Rush Hour 2](https://www.luogu.com.cn/problem/AT_abc204_e)：
用一点点数学知识和贪心优化 Dijskra。
- [Distance on Large Perfect Binary Tree](https://www.luogu.com.cn/problem/AT_abc220_e)：
数学题，可以直接推出式子。
- [Distance Sums 2](https://www.luogu.com.cn/problem/AT_abc220_f)：
最简单的换根 DP，求出从一个点开始的答案后可以 $O(1)$ 向子节点转移答案。
- [LEQ](https://www.luogu.com.cn/problem/AT_abc221_e)：
推一个式子，可以转化为类二维数点问题，可以离散化后用树状数组维护。
- [Red and Blue Tree](https://www.luogu.com.cn/problem/AT_abc222_e)：
先统计出每条边被走的次数，然后抽象成背包，需要特判。
- [Parenthesis Checking](https://www.luogu.com.cn/problem/AT_abc223_f)：
将 `(` 看作 $1$，`)` 看作 $-1$，用线段树维护区间和和区间前缀最小值，判是否均为 $0$。
- [Placing Rectangles](https://www.luogu.com.cn/problem/AT_abc223_e)：
分类讨论，枚举所有可能相对放置位置，可以 $O(1)$ 得解。
- [Problem where +s Separate Digits](https://www.luogu.com.cn/problem/AT_abc224_f)：
对于每个数计算成为个位，十位到更多位的方案数与贡献的乘积并累加。
- [フ](https://www.luogu.com.cn/problem/AT_abc225_e)：
将图形转化为原点的极角区间，然后用区间覆盖做。
- [Grid and Tokens](https://www.luogu.com.cn/problem/AT_abc205_f)：
比较裸的网络流，对行和列建点，是一个单位流量网络。
- [Digit Products](https://www.luogu.com.cn/problem/AT_abc208_e)：
数位 DP，套一遍板子，再分类讨论一下乘积的变化和前导零即可。
- [Shiritori](https://www.luogu.com.cn/problem/AT_abc209_e)：
基于字符串背景的图上博弈，从最终状态递推回去，用反拓扑序实现。
- [Power Pair](https://www.luogu.com.cn/problem/AT_abc212_g)：
数论题，需要用到原根及阶相关知识，转化为 $1+\sum\limits_{d|n}d\varphi(d)$。
- [Substrings](https://www.luogu.com.cn/problem/AT_abc214_f)：
比较简单的 DP，基于值域很小的字符串，用前缀和优化。
- [01Sequence](https://www.luogu.com.cn/problem/AT_abc216_g)：
直接贪心排序后往右放，暴力二分加树状数组填充，均摊复杂度是 $O(n\log ^2n)$。
- [Groups](https://www.luogu.com.cn/problem/AT_abc217_g)：
朴素 DP，在 $i$ 之前模 $m$ 与 $i$ 同余的数有 $\lfloor\frac{i-1}{m}\rfloor$ 个。
- [Make Pair](https://www.luogu.com.cn/problem/AT_abc217_f)：
区间 DP，贡献式合并时需要乘上系数 $C_{x+y}^x$，枚举时只计算偶数。
- [Game on Tree 2](https://www.luogu.com.cn/problem/AT_abc218_g)：
伪装成博弈论的 DP，dfs 到叶节点后用二分加树状数组实现中位数后逐层转递答案。
- [Propagation](https://www.luogu.com.cn/problem/AT_abc219_g)：
对点的度数进行根号分治，通过打标记和记录修改时间实现 $O(q\sqrt m)$。
- [Diameter set](https://www.luogu.com.cn/problem/AT_abc221_f)
求出直径后按直径的奇偶性分类讨论，可以在 $O(n)$ 时间内解决。
- [222](https://www.luogu.com.cn/problem/AT_abc222_g)
数学题，在推式子后用 BSGS 或暴力枚举 $\varphi$ 的因子判断可以做到 $O(\sqrt n \log n)$。
- [Expensive Expense](https://www.luogu.com.cn/problem/AT_abc222_f)
对每一个点建一个虚点后求树的直径，答案即为到直径两端点的最大值，需要特判。
- [Xor Query](https://www.luogu.com.cn/problem/AT_abc223_h)
离线分治，对于所有横跨区间中点的的询问直接用线性基合并求值，否则划分到左右区间，时间复杂度 $O(n\log ^2n)$。