BZOJ2959:长跑 – 题解

主要思路

乍一看没办法维护图的最大点权和,但是注意到没有删边操作,且注意到一个双连通分量可以被缩点,所以我们可以用 LCT 来维护双连通分量。

考虑开两个并查集,一个是双连通分量的并查集,标号为 \(0\);另外一个是维护连通性的并查集,标号为 \(1\)。

继续阅读BZOJ2959:长跑 – 题解

「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 – 题解