2024.5 做题记录

五一之后临时决定要来脱产。谢谢所有认可我的决定，支持我的人。

P1935 [国家集训队] 圈地计划

注意到 相邻两项不同就会产生贡献 的条件不好处理，所以考虑对行列进行黑白染色，将一种颜色格子的 \(a, b\) 交换，这样条件就变成了 相邻两项不同才会产生贡献。然后套用文理分科的做法就可以了。

图论

因为点可以重复经过，所以很自然的缩点然后再对内部含有重要边的 scc 拆点，对于一条重要边必须经过的限制实际就是下界为 \(1\)，建出来图然后跑有源汇上下界最小流即可。

关于图的建法，实际上还需要一个虚拟源汇对每个点连 INF 的边。并且这个源汇 不能 直接当作上下界最小流的虚拟源汇，还要再搞一组。（因为实际上第一组是原图为了算答案而构造的，也就是实际上是原图真正需要的点。）

CF1100F Ivan and Burgers

猫树分治，然后做一些线性基合并，复杂度大概是 \(O(n \log n \log V + q \log^2V)\)。

不知道暴力线段树维护线性基合并能不能过，能过就太无脑了。

好吃的题目

猫树分治练习题。注意到背包是支持合并的信息，并且容量最大只有 \(200\)，分治过程中维护背包即可，查询答案直接合并两边背包即可。

这里的合并不是真的合并，而是枚举一边的容量，复杂度是 \(O(V)\) 的。

[TJOI2018] 数学计算

有点类似线段树分治的想法。注意到一个数贡献的区间是一个连续段，直接打标记维护即可。

二分图 /【模板】线段树分治

每个边的贡献时间是个连续段，线段树分治然后用种类并查集维护二分图即可。

CF432D Prefixes and Suffixes

先求出原串的 Z 函数，然后考虑 即使前缀也是后缀 的限制实际就相当于 \(z[i] = n - i\)，其实就是匹配到了字符串的末尾。

然后用 Z 函数能很方便的求出每个前缀的出现次数，考虑对于每个 \(z[i] = k\)，其实说明的是 \(i\) 位置可以匹配长度为 \(1, 2, \cdots, k\) 长度的前缀，差分维护每个前缀的次数即可。