待补
CF1866
C
考虑在每个边权为 1 的边 \((u,v)\) 计算贡献。考虑 \((u,v)\) 被经过 \(m\) 次，表示为 \(r_1,\dots,r_m\) 。\(r_1,r_2\) 之间的 0 边被计算 \(1\) 次，\(r_2,r_3\) 之间的 0 边被计算 \(2\) 次，以此类推。这需要关注经过多少次 \((u,v)\) 不好计算，考虑 调整贡献计算方式 / 顺序 。形如 \(\sum a_i\) 显然可以放在二维平面上转化，这里贡献表示为 \(\sum a_ii\)，那按 行 考虑，只需要对于每条路径，计算它后面经过多少 0 边即可。设 \(f_u\) 表示 \(u\) 往后直到离开 \(u\) 的 0 边数量，\(g_u\) 表示从 \(1\) 到 \(u\) 所有路径的贡献和，\(h_u\) 表示从 \(1\) 到 \(u\) 的方案数，拓扑排序转移即可。
另外一种思路：设 \(f_u\) 表示进入 \(u\) 知道离开 \(u\) 的贡献，转移即可。类似树上按照一定顺序游走的 DP。
总结：调整贡献计算方式 / 顺序，放在二维平面考虑，按 行 / 列 考虑，DAG 上 DP 一般两种顺序：拓扑序，反拓扑序
G
二分图匹配，点连向区间。从小到大考虑每个点，匹配包含它右端点最小的区间。
我的做法：判断存在二分图完美匹配，考虑 hall 定理。由于 \(\sum m\ge S\)，我们对点考虑。限制有 \(2^{|S|}\) 个，复杂度过高，考虑减少冗余限制。分讨特殊情况，考虑在同一个车站的点，连边相同，那么限制最强的显然是将同一个车站的点一起考虑，限制数变为 \(2^{n}\) 。考虑对应区间如果划分成若干连通块，显然只需要考虑每个连通块分别成立即可，那么现在只需要关注区间构成连通块的限制。如果我们确定了区间的 \(l,r\)，那么只要包含在 \([l,r]\) 的区间都会被加上，限制变为 \(n^2\) 个。二元，考虑固定 \(l\)，变化 \(r\)，对每个 \(l\) 维护当前 \(r\) 的值。hall 定理成立的条件是 \(|S|\le |N(S)|\)，对于区间 \(l,r\)，需要满足 \(w\le m(r-l+1)\) 转化成 \(mr\ge w+m(l-1)\)，其中 \(r\) 为枚举的量，动态维护 \(w+m(l-1)\) 即可。注意不为连通块不影响正确性。
题解区的做法：二分图匹配，构建网络流，考虑 模拟最大流，转化为 最小割 。容易发现只能割左部 / 右部的边，不能割中间的边。那么就相当于选择一些点，贡献为 \(m\)，还有一些区间，如果没有完全被覆盖，贡献为 \(a_i\)，求最小贡献。设 \(f_i\) 表示考虑了 \(\le i\) 的区间选择情况，需要关注区间是否被完全包含。加上不被完全包含的贡献是难算的，正难则反，容斥，减去被完全包含的区间贡献，线段树优化 DP 。
总结：模拟最大流转化最小割，正难则反，容斥
H
有标号，考虑转化为无标号，也就是集合，钦定顺序。考虑枚举后 \(t\) 个集合非空，容易发现那么 \(t\) 个集合必然不同，所以可以将无标号转化为有标号。关注斜率为 \(-1\) 的直线，发现方案可以转化为每个直线的方案数的乘积，这可以 \(\mathcal{O}(\log n)\) 计算，复杂度 \(\mathcal{O}(n\log n)\) 。
总结：有标号转化为无标号再排列；无标号转化为有标号除以排列，无标号相当于集合，考虑 钦定顺序（升序 / 降序）
I
关注量，考虑特殊情况，分讨
博弈论，设 SG 函数 \(a_{i,j}\) 。关注 \(a_{i,j}\)，若 \(a_{i,j}=0\)，那么 \(\forall\; k>j,a_{i,k}=1,\forall\;k>j,a_{k,j}=1\)，那么得到右下角的矩形中每列都存在 \(0\)，那么 \(\forall\;k<i,l>j,a_{k,l}=1\)，那么得到从下到上每行至多存在一个非关键点的必败点，且横坐标递减，模拟即可。
L
由于 \(k\le 2000\)，考虑枚举 \(k\) 。暴力模拟不行，考虑加快模拟过程。关注一轮，当我们知道当前 L 在 \(r\) 处，C 在 \(s\) 处，可以解一元一次不等式得到此轮的贡献且可以得到下一轮的 \(r,s\) 。考虑最多有 \(k\) 轮，如果重复，那么后面就没有贡献了，复杂度 \(\mathcal{O}(n^2)\) 。
总结：加快模拟过程，关注 整体。