A
发现 \(a\) 的线性基的大小很大,枚举一下线性基外面的数选或者不选,判断一下能否构成 \(k\) 个区间即可。
B
我们找出所有的三元组 \((x, y, c)\) 代表某一列中 \(x\) 行和 \(y\) 行颜色都是 \(c\)。
首先三元组的种数只有 \(2n \times (2n - 1) / 2 \times n = n^2 \times (2n - 1)\) 种。
我们接下来证明一列至少会占用 \(n\) 种:
$ \sum c_i = 2n $
\[\begin{aligned} \sum \frac{c_i(c_i - 1)}{2} &= \frac{\sum c_i^2}{2} - \frac{\sum c_i}{2}\\ &\ge \frac{(\sum c_i)^2}{2n} - n\ \text{(Cauchy–Schwarz inequality)}\\ &= n \end{aligned} \]所以 \(m > n \times (2n - 1)\) 时必然无解。
下面给出 \(m = n \times (2n - 1)\) 的构造。
不妨把一对颜色相同的点看作一个匹配,那么如果我们能找出 \(K_{2n}\) 的 \(2n - 1\) 个边集不相交的匹配,每一组匹配都可以循环着染色染 \(n\) 列。
(以下点的下标从 \(0\) 开始)构造匹配是容易的:对 \(i\in [0, 2n - 2]\) 我们找出满足 \(x + y \equiv i \pmod{(2n - 1)}\) 的每一对 \((x, y)\) 根据同余的性质一定有 \(n - 1\) 对,而 \(i \times 2^{-1}\) 一定没有匹配,和 \(2n - 1\) 匹配即可。这样对于每一个 \(i\) 我们都找到了一组匹配,且它们边集不交。
C
首先我们不妨设 \(a_i \le b_i\)。
我们讨论一下一对数 \(a_i, b_i, a_j, b_j\) 的贡献:首先两个都交换的话贡献不变,如果 \(a_i \le b_i \le a_j \le b_j\) 交换了某一组 \((a, b)\) 答案不变,如果 \(a_i \le a_j \le b_i \le b_j\) 交换了某一组 \((a, b)\) 答案加上 \(b_i - a_j\),如果 \(a_i \le a_j \le b_j \le b_i\) 交换了某一组 \((a, b)\) 答案加上 \(b_j - a_j\)。
概括一下,如果交换了其中一组 \((a,b)\) 那么 \((a_i, b_i)\) 和 \((a_j, b_j)\) 之间的贡献会加上这两条线段的交的大小。
现在问题变成了:给 \(n\) 个线段,每条线段可以染成黑白两种颜色,使每一对异色线段的交的和最大。
我们在数轴上连接 \((a_i, b_i)\),我们把每个连续段拿出来(类似扫描线那样),如果它被 \((a_i, b_i)\) 这样的边覆盖了 \(k\) 次,那么它的贡献的上界是 \(len \times \left\lceil \frac{k}{2} \right\rceil \times \left\lfloor \frac{k}{2} \right\rfloor\)。
现在通过构造来说明:每个上界都可以达到。
如果一个小段被覆盖了奇数次,那就额外在这个小段左右端点之间连一条边。
这样,每个点的度数都是偶数,它的每个连通块都有欧拉回路。所以被覆盖了 \(k\) 次(包括额外边)的小段会被从左往右走 \(\frac{k}{2}\) 次,从右往左走 \(\frac{k}{2}\) 次。而它只会被额外边覆盖一次,所以把从左往右的染成白色,从右往左的染成黑色,便能达到上界了。
D
先考虑如何求一个串的价值:
首先 \(\texttt{((}\) 之间的贡献和 \(\texttt{))}\) 之间的贡献是好算的。
我们考虑计算出对于长度 \(n\) 的所有合法的括号序列的 \(\texttt{)(}\) 子序列数量,以及原来括号序列的 \(\texttt{()}\) 的子序列数量,那么就很容易算出答案。
此时发现一个串的价值为 \(Ax + B\) 的形式,其中 \(x\) 为该串的 \(\texttt{()}\) 的子序列数量。于是可以对于每一个 \(\texttt{()}\) 都算上贡献,就能做原问题了。
问题变成了如何求长度 \(i\) 的所有合法的括号序列的 \(\texttt{)(}\) 子序列数量和。
设 Catalan 数列为 \(f\),生成函数为 \(F(x)\),设答案数列(所有 \(i\) 个左括号的合法括号序的 \(\texttt{)(}\) 子序列的数目之和)为 \(g\),生成函数为 \(G(x)\)。
考虑合法括号序的构造:在一个合法括号序外加一左一右两个括号,没有贡献;两个合法括号序 \(A,B\) 拼接成 \(AB\),贡献为 \(\operatorname{len}(A)\times\operatorname{len}(B)\)。
注意到形如 \(ABC\) 的序列只能计算一次,故我们强制钦定只算形如 \(A(B)\) 的括号序,这样多个括号序拼接只会计算最后一次。
考虑递推式为 \(g_i = \sum f_jf_{i - j - 1}j(i - j) + f_jg_{i - j - 1} + f_{i - j - 1}g_j\)。
得到生成函数 \(G(x) = xF^\prime(x)x(xF(x))^\prime + 2xF(x)G(x)\)。
将 \(xF(x)\) 带入 \(\frac{1-\sqrt{1-4x}}{2}\) 得到 \(G(x) = \frac{x^2F^\prime(x)}{1 - 4x}\)。
可以直接线性递推。
而动态维护原序列 \(\texttt{()}\) 数量也是容易的,因为交换 \(x\) 和 \(y\) 两个位置改变量只能是 \(0\) 或者 \(\pm (y - x)\)。
时间复杂度 \(\mathrm{O}(n + q)\)
标签:le,frac,题解,texttt,times,括号,2n From: https://www.cnblogs.com/AC7-/p/16870799.html