主要思路
乍一看没办法维护图的最大点权和，但是注意到没有删边操作，且注意到一个双连通分量可以被缩点，所以我们可以用 LCT 来维护双连通分量。
考虑开两个并查集，一个是双连通分量的并查集，标号为 \(0\)；另外一个是维护连通性的并查集，标号为 \(1\)。
继续阅读BZOJ2959:长跑 – 题解分类：OI
「Codeforces 461E」Appleman and a Game – 题解
主要思路
首先，不考虑原问题，只考虑最优策略，显然是当前能匹配的串越长越好。所以可以考虑二分答案，算当前拼接次数下能拼出来的最长的串，再将其与 \(n\) 进行比较。
继续阅读「Codeforces 461E」Appleman and a Game – 题解AtCoder Grand Contest 043 – 解题报告
A – Range Flip Find Route
思博题。考虑最后的路径肯定是多个黑白子路径的拼接，那么路径的代价就是进入黑色子路径的次数，那么我们只需要建图的时候给白色入黑色的边赋 \(1\) 的权即可。
继续阅读AtCoder Grand Contest 043 – 解题报告「Codeforces 666C」Codeword – 题解
主要思路
就这？思博题。
总觉得做过啊。答案很显然跟字符无关，我们需要固定最左边的子序列，然后枚举最后一位，得出结论（子序列 \(T\)、目标串长 \(n\)）：
\[ ans = \sum_{i = |T|}^n 25^{i – |T|} \times 26^{n – i} {i – 1 \choose k – 1} \]
考虑把 \(n\) 提出来：
\[ ans = 26^n \sum_{i = |T|}^n 25^{i – |T|} \times 26^{-i} {i – 1 \choose k – 1} \]
发现一个重要性质：\(\sum |T| \leq 10^5\)，所以对于不同的 \(|T|\)，最好情况下个数为 \(\Theta(\sqrt{n})\)。那么既然 \(n\) 可以被独立出来，那么最后复杂度就是 \(\Theta(|T|\sqrt{n})\)。
继续阅读「Codeforces 666C」Codeword – 题解BZOJ2138:stone – 题解
主要思路
首先可以发现这个东西可以被认为是一个二分图的模型，只不过现在我们需要快速算其最大匹配。那么根据 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} \]
这个东西用线段树维护即可。
继续阅读BZOJ2138:stone – 题解「AtCoder Regular Contest 090F」Number of Digits – 题解
主要思路
这个题还蛮有意思。
首先有个暴力，\(l\) 在 \(10^7\) 内可以直接 two-pointers；如果在 \(10^7\) 以上，那么发现 \(f(r) – f(l) \leq 1\)。那么我们可以考虑枚举这个连续段的长 \(L = x + y\)，其中 \(x\) 是 \(i\) 个 \(0\) 的部分，而 \(y\) 是 \(i + 1\) 个 \(0\) 的部分。有个等式：\(x \times i + y \times (i + 1) = (x + y)i + y = Li + y = S\)。所以枚举 \(L\) 的时候，如果 \(S \bmod L \equiv 0\)，那么说明 \(y = 0\)，你就把 \(10^i\) 内的左端点个数算出来（其实就是多减一个 \(L – 1\)）。如果 \(S \bmod L \neq 0\)，那么说明 \(x, y\) 确定了，那么就直接 ++ 即可。
继续阅读「AtCoder Regular Contest 090F」Number of Digits – 题解