P8037 [COCI2015-2016#7] Prokletnik
只考虑计算 L 是 min R 是 max 的情况，另一种情况是对称的。
考虑维护一个单调递增的单调栈，这样我们就可以维护出当前所有 “存活” 着的点，然后再考虑用一个线段树维护现在存活的点的最远可行的 r。
对于不存活的点直接在他不存活的时候把贡献记录一下就好了。
CF1210F2
一个二分图，左右部各 \(n\) 个点，\(i \leftrightarrow j\) 的边有 \(p_{i,j}\) 的概率出现，求出该二分图有完美匹配的概率。
\(n \le 7\)。
先讲一下 F1 的 \(n \le 6\) 的做法。
发现 \(n \times \frac{n}{2} \le 18\)，\(\binom{n}{\frac{n}{2}} \le 20\)。
引导我们想到折半。
我们可以求出对于右边点的上半(13)和下半(47)匹配左边三元组的情况为 \(S\) 的概率，和匹配其补集的概率。
然后就可以计算出没有完美匹配的概率。
然后考虑 \(n = 7\) 怎么做。
发现其实我们没有必要对于每种 \(S\) 都计算出这个概率，比如当 \(L(1,2) L(3,4)\) 都匹配 \(R(1,2)\) 时 \(L(1,3)\) 和 \(L(1,4)\) 中至少有一个匹配 \(R(1,2)\)。这启发我们极大的匹配状态可能很少。
事实证明最多只有 \(3 \times 10^5\) 种。
于是我们可以考虑每次加入一个右边的点然后维护所有可能的匹配状态。
时间复杂度 \(\mathcal{O}(n^2 2^n S)\)，其中 \(S \le 3 \times 10^5\)。
CF1210G
首先破环成链。
然后考虑 \(n \leftarrow 1\) 的流量。
设其为 \(c\)，那么我们就可以进行 dp 了。
然后我们发现这个 dp 是一个很经典的 slope trick 形式，可以分别维护极小值段左右两边斜率变化点，和这两个的偏移量。
然后我们可以发现答案关于 \(c\) 也是一个下凸函数，所以我们可以三分。
时间复杂度 \(\mathcal{O}(n \log n (\log {n} + \log{V}))\)。
CF1842H
假设我们现在知道一些点 \(< 0.5\)，一些点 \(> 0.5\)。
那么显然同色点之间不会有限制。
然后我们惊奇的发现，假设 \(x\) 是 \(< 0.5\) 的，两种限制变成了 \(x \le 1-y\) 和 \(x \ge 1-y\)。那么我们就可以设 \(b_x = (a_x > 0.5 ? 1 - a_x : a_x)\)。
我们发现所有限制变成了 \(b_x\) 之间的大小限制，那么如果染色方案确定其实就变成了拓扑序计数了。
但是现在染色方案不确定，我们发现其实也问题不大。
我们可以考虑钦定染色顺序，即我们钦定从 \(\lvert b_x \rvert\) 小到大加入每个 \(x\)。
那么显然如果有一种限制满足就能使得该种点染上某种颜色，因为我们并不关心 \(S\) 中其颜色到底是什么。
CF1929F
倍数关系可以考虑建出 dag 来考虑。
发现对于一个联通块，一定可以删到只剩无出度的点数 \(+1\) 个点。
然后我们再发现因为 \(\le 30\) 的质数只有 \(15\) 个，所以真正有意义的初始点只有 \(15\) 个。
于是我们就可以对每个联通块做一个状压 dp，再记录一个当前已经放了多少个点进入图中。
转移的时候讨论这一次操作有没有使得 \(S\) 扩大即可。
ecfinal2023 C Equal sum
考虑最朴素的 \(\mathcal{O}(n^3V)\) 的 dp 能怎么优化。
发现其实记录前缀差这一维我们可以只开到 \(\mathcal{O}(V)\)。
可以考虑这样子 dp，如果我们当前 \(x > 0\)，我们就交给 \(b\) 放数字，如果 \(x \le 0\)，我们就交给 \(a\) 放数字，可以发现这样不仅满足了不重不漏同时还减小了状态，非常厉害。
ecfinal2023 I balance
考虑最大值和最小值之间的路径，显然其至少有 \(max - min\) 的贡献，所以其他边一定不能有贡献。
然后考虑这能带来什么强的限制，发现一件事情，一个边双内部如果有两个点值不相同，那么由于他们之间有两条边不相交的路径，那么一定会出现多余的贡献，一定会使得整个图不合法，所以说一个边双内值一定要相同。
于是我们可以边双缩点之后然后 dp 一条合法的 min 到 max 的路径出来即可。