Marshland
神网络流……思维固化导致没想出来……
题意
在一个 $n \times m$ 的网格内，每个格子有权值 $w_{i, j}$。保证 $i+j$ 为偶数的点权值为 $0$ .
要用最多 $m$ 个 $\text{L}$ 形的石头对网格进行部分的覆盖。石头不能重叠。每块石头会产生拐角处权值的收益。
有 $k$ 个格子不能被石头覆盖。求最大收益。
$n \le 50$.
思路
可以看出显然的匹配模型，但是把拐角放在二分图左边，另外2个点放在二分图右边根本做不了。因为有条边只能取 $0, 2$ 作为流量，而这是不可能的。
这种时候要设法把 $0, 2$ 变成 $1, 1$ ，也就是用流量平衡来保证 $0, 2$ 的限制，使得一个单位流量进入拐角，一个单位流量流出拐角。考虑按照奇偶对空点染色。对于剩下的点要保证只被一个 $\text{L}$ 覆盖。拆点后即可满足。跑最小费用流就可以了。
Party
坑着。
Platform
后缀数组题，由于考试的时候对后缀数组性质生疏没能想出来……其实思路很直接……
题意
有一个字符串，每个位置有一个权值。问有多少满足以下条件的子串：
- 长度 $\ge 1$
- 权值和 $=$ 该子串在原串所有子串中字典序的降序排名
注意相同的子串对于排名只有 $1$ 的贡献。
$n \le 2 \times 10^5$，且保证符合要求的子串数目不超过 $2 \times 10^5$.
思路
考虑枚举左端点，并且二分关于右端点函数的零点，显然子串和递增，且子串排名递减。
对于每个子串我们要查出它的排名。
为了方便处理，我们 钦定 当前子串的前缀字典序大于它自己。于是二分找出满足LCP长度限制的所有后缀在SA中最左边一个（因为相同子串对排名总贡献为1）。
找到这个之后，此后部分可以看作一个子后缀数组。利用Height数组的后缀和，可以 $O(1)$ 计算。
注意我们刚才 钦定 的东西，要额外加上它对排名的贡献。
总时间复杂度为 $O(n \lg^2 n)$ 。
