Graph Transpositions
对于第二种操作的数量 \(y\)，如果 \(y>18\)，那么只需要保证 \(y\) 最小的前提下跑最短路即可。
分层图跑一下，最后一层代表 \(y\ge 19\) 的层。
Min-Fund Prison (Hard)
\(k\) 是固定的。对于缩完边双的森林，我们使用 dp，\(f_{i,j,k}\) 表示前 \(i\) 棵树，是否在树上割过边，能否凑出大小为 \(k\) 的子树。bitset 优化，复杂度 \(O(\frac{n^2}{w})\)。
Babysitting
二分，2-SAT。
Best Subsequence
转化为 \(n-\mathrm{zerocount}(...)+60\)。
建立二分图，左边是 \(n\) 个点，右边是 \(60\) 个数位。如果我们选了 \(x\)，且 \(x_i=1\)，那么 \(x\) 和数位 \(i\) 无法同时产生贡献，那么连一条边。
最后我们需要求这张图最大独立集大小 - 60。
Removal Sequences
时光倒流，最后一定删去 \(a_i=0\) 的点，那么与 \(i\) 相连的边一定在这之前被删除，且 \(i\) 的邻居在被删除之前一定保留了到 \(i\) 的那条边。将 \(i\) 删去，然后将 \(i\) 邻居的 \(a\) 减去一，即可递归子问题。
根据这个删除顺序我们可以得到一个 DAG。如果两个点 \((x,y)\) 不是美好的，当且仅当 \(x,y\) 之间存在一条路径，用 bitset 解决。复杂度 \(O(\frac{n^2}{w})\)。