[省选联考 2020 B 卷] 丁香之路
对于固定起点、终点 \(s,t\)，相当于给一个边集 \(E_0\)，找一个尽可能小的边集 \(E\supseteq E_0\) 使得 \(E\) 对应的子图中存在一条 \(s-t\) 的欧拉路 .
考虑先加一条 \((s,t)\) 转为欧拉回路，然后首先把 \(E\) 的每个点度数补成偶数且连通尽量多的点：考虑每个 \(2\nmid\deg(u)\) 的 \(u\)，然后按顺序两两匹配，对于一组 \((u,v)\)，依次连 \((u,u+1),\cdots,(v-1,v)\) 来使得它们的度数奇偶性翻转 .
操作完之后只需要再连一些边使得每个度数不为 0 的点都连通，这个可以使用最小生成树简单解决 .
时间复杂度 \(\tilde\Theta(n+m^2)\) .
[JSOI2019] 精准预测
类似 2-SAT 地，对每个时刻 \(t\) 上的居民 \(x\) 建立结点 \(\operatorname{alive}(t,x),\operatorname{dead}(t,x)\)，然后刻画出 0 操作和 1 操作还有不能复活的限制之后就是问对于每个 \(\operatorname{alive}(T+1,x)\) 有多少个 \(y\) 使得 \(\operatorname{alive}(T+1,x),\operatorname{alive}(T+1,y)\) 都不能到 \(\operatorname{dead}(T+1,y)\) . 显然只有 \(O(n+m)\) 个点是关键的，那么大力建图后直接 bitset 跑 DAG 可达性就可以了 .
由于这个题比较毒瘤所以需要一系列卡常：
- 时间上：需要使用 DFS 进行 DP，不要写 BFS 的拓扑排序；注意到只有限制中作为 \(x\) 的位置才可能有用，\(y\) 的位置并没有什么用，于是可以把每个 \(y\) 的限制对应的时间改成离它最近的作为 \(x\) 操作数的时间，这个操作大概可以让点数除以二 .
- 空间上：由于开不下全的 bitset 所以需要分段做，令块长为 \(B\) 则每次只记录 \(B\) 个点的可达性，做 \(\frac nB\) 次 .
[AGC026D] Histogram Coloring
先考虑如果矩形是整的那么就考虑每行相当于必须填下一行的 flip，如果下一行全同色则也可以和下一行填一样的 .
那么对于任意棋盘也可以考虑每次填最下面一行，但是此处删掉一行之后序列可能会分裂成若干部分，此处可以递归进入子问题 . 大概是一个笛卡尔树的结构 .
[AGC049D] Convex Sequence
如果 \(a\) 单调增的话就是要求 \(a\) 的差分数组单调增并且它的二阶前缀和等于 \(m\)，那么 Abel 变换拆一下贡献可以得到方案数为 \(\displaystyle p(m)=[x^m]\prod_{k\ge1}\dfrac{1}{1-x^{k(k+1)/2}}\) .
对于原题来说考虑枚举最小值就变成了两个单调增的问题卷起来，相当于要算 \(O(n)\) 个：
\[[x^m]\prod_{k=1}^a\dfrac{1}{1-x^{k(k+1)/2}}\prod_{k=1}^b\dfrac{1}{1-x^{k(k+1)/2}} \]然而发现本质不同的 \((a,b)\) 对只有 \(O(\sqrt m)\) 种，于是直接动态维护每个位置的系数，只需要每次乘或除一个 \(\frac1{1-x^c}\) .
总时间复杂度 \(O(m\sqrt m)\) 可以通过 . 我们 GF 批是这样的