仅存不会的题。
AtCoder [ARC099B] Snuke Numbers
一种题目：要求 列出 前 \(k\) 小 的所有满足条件的数。
这时候有个 Trick：可以考虑求一个 \(f(n)\) 表示 \(\ge n\) 的最小的满足条件的数。这样就可以从 \(f(1)\) 出发跳 \(k-1\) 次 \(f(n+1)\) 求出前 \(k\) 小的 \(n\)。
此题中，\(f(n)\) 即为 \(\ge n\) 的数中最小化 \(\dfrac{n}{S(n)}\) 的整数 \(n\)，其中 \(S\) 为十进制下数位和。而 \(f\) 容易贪心求出，依次将 \(n\) 的最后若干位改为 \(9\) 即可。
AtCoder [ARC099C] Independence
将一给定无向图 按点集 分成两个 完全子图，判断是否可行；若可行，最小化 被任一子图完全包含的边 的数目。\(n\le700,m\le \dfrac{n(n-1)}{2}\)
众所周知 团 即为 补图 中的 独立集。观察 \(n,m\) 的范围可以想到建立补图。
这是因为考虑套路：把 划分问题转化为染色问题。任一对同色节点相邻 变为补图中 任一对同色节点不相邻，后者即相当于：要求划分为一张二分图。这可以用染色法轻易解决。
断言：对于一个连通二分图，将其 二染色 的方案是 唯一 的（除交换左右部外）。
引理：对于一个非连通二分图，其每个连通块均为二分图（允许有一部为空）。
因此可以对所有连通块判断是否为二分图。若有不是者，则整个划分不可行。否则可以求出每个连通块的两部分点数 \(x,y\)。即转化为适当决定每组 \(x,y\) 分别 加入整个划分的左部还是右部。
回到此题，相当于考虑两个点集大小为 \(a,b\)，最小化 \(\dfrac{a(a-1)+b(b-1)}{2}\)。由于 \(n=a+b\) 及基本不等式，简单推式子可知相当于最小化 \(|a-b|\)。
这时候已经是 集合二划分最小化大小差 的板子题，直接用一个 可行性背包 就可以解决。
AtCoder [ARC099D] Eating Symbols Hard
对于这种状态内维护一个序列的逆题，直接对于进行序列哈希。发现传统哈希即可支持按位左移 / 右移 / 单点加减 / 差分，即得到 区间 哈希值，但是还需要考虑预处理 前缀 的位移和 \(p_i\) 用来计算，设基数为 \(x\)，即：
\[h_{[l,r]}=\dfrac{h_r-h_{l-1}}{x^{p_{l-1}}} \]设 \(k=h_{[1,n]}=h_n\)，即统计使上式等于 \(k\) 的 \((l,r)\) 数目。为了做到 \(O(n)\)，考虑：
\[k=\dfrac{h_r-h_{l-1}}{x^{p_{l-1}}} \]\[h_r=k \cdot x^{p_{l-1}} + h_{l-1} \]扫描线加上 map 随便统计即可。注意 Hash 强度，考虑双模数 / 双基底。