首先可以发现这个东西可以被认为是一个二分图的模型，只不过现在我们需要快速算其最大匹配。那么根据 Hall 定理，如果对于任意一个左部点 \(x \in U, |U| < |V|\)，其连接的右端点集合 \(M\) 满足 \(|M| > |U|\)，那么就存在完美匹配。
这个题有个性质：区间互不包含。所以满足 Hall 定理其实就需要满足对于每个线段都存在 \(\sum_{i = l}^r b_i \leq \sum_{i = L[l]}^{R[r]} a_i\)，其中 \(b_i\) 是对于第 \(i\) 根线段我们取了 \(b_i\) 个石子。
我们可以写成一个前缀和进行移项：
\[ p^b = \sum b_i, p^a = \sum a_i \\ p^b_{r} – p^b_{l – 1} \leq p^a_{R[r]} – p^b_{L[l] – 1} \\ p^b_{r} – p^a_{R[r]} \leq p^b_{l – 1} – p^b_{L[l] – 1} \]
这个东西用线段树维护即可。
Continue reading →看到这个很小的模数就知道肯定是个 Trick 题，一定不会让你去跑一般图的（估计是 NPC）。
首先，我们可以设颜色未标号的、用了 \(i\) 种颜色的方案数为 \(f_i\)，那么答案就是：
\[ ans = \sum_{i = 1}^k f_i k^{\underline{i}} \]
发现这个东西在 \(i > 2\) 时就直接被模成了 \(0\)。我们只需要算 \(f_1, f_2\) 即可。其中 \(f_1 = [m = 0]\)。\(f_2\) 的方案数等价于二分图的双部染色的方案数。所以，我们跑一边二分图然后算 \(2^b\) 即可，\(b\) 是连通块次数。
Continue reading →这道题直接去想性质不好想，因为贪心的话、找到两个大小相近的团没什么性质。我们可以考虑建一张反图。如果这是个二分图，那么左右部恰好可以作为题中的两个 state。然而，意识到并不保证是一张连通的二分图，所以我们可以用一些连通块来拼成两个 state。那么，我们可以用个背包搞搞，再最后算算答案即可。（就不需要贪心的构造两个大小相近的团了，全部都算一遍即可）。
这道题乍一看不是很能做，因为摆放状态很多。然而，计算机科学这种东西解决不了问题的时候不讲究正解，只讲究近似。所以，我们可以枚举一个旋转角 \(\theta\) 来决定最终摆放的形态。枚举之后就可以直接二分费用并建边做二分图。
真的是玄妙重重。
我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。
在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。