CSP2019-S Solution

还是咕了一些题……

Day1

T1 code

观察到格雷码顺次排列时,每一位均存在循环节,如第 0 位按照 0110 循环,第 1 位按照 00111100 循环,第 2 位则是 0000111111110000,于是按位对循环节长度取余后依次输出即可。

$O(n)$。

T2 brackets

一个基本的思路是对于一个右括号节点 $u$,找到与其匹配的左括号祖先 $v$,此时其对答案的贡献为当前这对括号加上 $v$ 上面与 $v$ 连续的括号匹配数量。

「连续」的要求是那些括号中间不能有空位。比如 (()())()(),若 $u$ 为最后一个,$v$ 为倒数第二个,那么连续括号匹配数量为 2((()()) 这个串左右两边的那对括号和 () 接在一起,且中间没有空位)。而如果变成 (()())(()() 就只有一个了,因为中间插入了一个左括号使得 (()())() 不连续了。

或者用代码来描述:设 match[u] 表示与 $u$ 所匹配的左括号(当 $u$ 为右括号时值为 0),则对答案的贡献可以用 cnt 来表示。cnt 求法如下:

1
2
3
int cnt = 0;
while (u != 0)
++cnt, u = fa[match[u]];

正确性应该很好证,因为对子串数目产生新的贡献只能这么产生。

于是对该树进行 DFS,用一个栈维护从根到该节点的左括号情况。若当前节点是左括号直接加入栈内,右括号则取出栈顶的左括号与其匹配成为一对括号并算上贡献。回溯时撤销这一步操作就行了。

当然没必要每次像上面的代码一样 $O(n ^2)$ 地跳,直接把 cnt 存为数组,每次新的答案就是 cnt[fa[match[u]]] + 1cnt 更新为这个新的答案即可。

$O(n)$。核心代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void DFS(int u)
{
ans[u] = ans[fa[u]];
if (str[u] == '(')
stk[++top] = u;
else if (top)
{
match[u] = stk[top--];
cnt[u] = 1 + cnt[fa[match[u]]];
ans[u] += cnt[u];
}
for (int i = head[u]; i; i = nxt[i])
DFS(to[i]);
if (str[u] == '(')
--top;
else if (match[u])
stk[++top] = match[u];
}

Day2

T1 meal

看错题差点死在这里……一开始看的题目是每个烹饪方式只能选一个食材,但是可以做多道菜……

注意到题目所给的第三个条件比较恶心。对这个条件考虑补集转换,用任选方案数(注意,这里的任选还是得满足第 1,2 个条件)减去不满足第三个条件的方案数。

由于该条件的特殊性,不满足条件的食材只会出现一种。于是首先枚举是哪个食材不满足条件,也就等价于这个食材的菜数比其他所有食材的菜数和更大。

设这是第 $k$ 个食材。这样就很好做 DP 了:设 $f(i, j)$ 表示选完了前 $i$ 个烹饪方式的菜的情况下,当前第 $k$ 个食材的菜数比其他菜数的总和多 $j$ 道的方案数。这里的 $j$ 可以为负数。

那么当前烹饪方式有不选菜、选第 $k$ 个食材的菜、选其他食材的菜,有转移:

$$
f(i, j) = f(i - 1, j) + f(i - 1, j - 1) * a _{i, k} + f(i - 1, j + 1) * (sum _i - a _{i, k})
$$

其中 $sum _i$ 表示第 $i$ 个烹饪方式的菜的总和。

任选方案数为 $\prod \limits _{i = 1} ^n (sum _i + 1) - 1$。减 1 是因为不允许不选菜。

$O(n ^2 m)$。

T2 partition

首先有一个暴力 DP: 设 $f(i, j)$ 表示已经划分了前 $i$ 个数的段,最后一段以 $j$ 开头的最小总运行时间。设 $S(j, i) = \sum \limits _{k = j} ^i a _k$,有转移:

$$
f(i, j) = \min _{0 < k < j, S(j, i) \ge S(k, j - 1)} {f(j - 1, k)} + S(j, i) ^2
$$

直接按方程转移是 $O(n ^3)$ 的。注意到若将 $j$ 从 $i$ 到 $1$ 逆顺序转移,能够贡献的那些 $k$ 不断变多。于是设置一个指针 $p$,初值为 $i$,每次 $j \gets j - 1$ 时调整 $p$ 的位置不断向左走,即可做到均摊下 $O(1)$ 转移,复杂度 $O(n ^2)$。

状态数很明显的需要优化,打表可以发现:能够转移到其他状态的 $f(i, j)$ 必定满足 $f(i, j)$ 是最后一个合法的状态,即 $f(i, j + x)$ 均是不合法状态。换句话说,只要让以 $i$ 结尾的最后一段划出来的总和尽可能小,就可以构造出一种最优方案。

myy 的证明

于是重设状态:设 $g _i$ 表示最大的满足以 $g _i$ 作为最后一段的开头能够合法的位置。有转移:

$$
g _i = \max _{0 < j < i, S(j + 1, i) \ge S(g _j, j)} {j} + 1
$$

设 $P _i = \sum \limits _{j = 1} ^i a _i$,将 $S(j + 1, i) \ge S(g _j, j)$ 变形为 $P _i \ge 2P _j - P _{g _j}$。再设 $T _i = 2P _i - P _{g _i}$。

用数据结构维护 $T$ 固然可行,但复杂度仍不够优秀。注意到其单调性:由于是取 $\max$ 并且是从前往后转移的,那么对于当前状态 $i$ 而言,前面的 $j$ 若有 $T _j \ge T _i$ 则 $j$ 一定不会比 $i$ 更优。

这是个典型的单调队列优化转移的情况。队尾出队按 $T$ 比较即可,当队头的后一个元素 $u$ 满足 $T _u < P _i$ 时可知队头已经不会再产生贡献,将队头出队。

注意一开始要放入 0,并设 $g _0 = 1$ 以减少边界情况的处理。

这样可以顺利获得 88pts。再考虑高精度的问题。

可以考虑将答案表示为 $a \times 10 ^{18} + b$ 的形式并进行运算。加法直接将 $a, b$ 分别相加(注意 $b > 10 ^{18}$ 时得进位)。乘法则是一个 long long 范围内数 $x$ 的平方,将 $x$ 表示为 $a \times 10 ^9 + b$ 的形式则有(将 $10 ^9$ 省略为 $B$):

$$
\begin{aligned}
& x ^2 \\
=& (aB + b) ^2 \\
=& a ^2 B ^2 + 2abB + b ^2 \\
=& a ^2 B ^2 + 2(a’B + b’)B + b ^2 \\
=& (a ^2 + 2a’) B ^2 + (2b’B + b ^2) \\
=& (a ^2 + 2a’) 10 ^{18} + (2b’B + b ^2)
\end{aligned}
$$

其中 $ab = a’ \times 10 ^9 + b’$。这样即可避免高精度问题。

同样的,$2b’B + b ^2$ 处注意进位。另外由于可以直接求出分段情况(也就是 $g _i$),不需要存答案数组,也避免了炸空间的问题。

T3 centriod

下面用 $son(x)$ 表示 $x$ 的重儿子,$s _x$ 表示 $x$ 子树大小。特别的,对叶子定义其 $son(x) = 0$,且 $s _0 = 0$,减少特判。

考虑到三个重要结论:

  1. 一棵树任意定根,重心一定在根节点所在的重链上。
  2. 两个重心一定相邻。
  3. 点 $u$ 满足 $s _u \ge \lceil \frac n 2 \rceil, s _{son(u)} \le \lfloor \frac n 2 \rfloor$,是其为重心的充要条件。

第一个结论要想到也不难,随手画一下重剖的图会发现这看上去就很对。第二个是常识。第三个实际上就是「其分裂出来的树均不超过 $\lfloor \frac n 2 \rfloor$」的另一说法。

由于第二个的存在,只需要求出深度较深的重心,$O(1)$ 地检查一下他的父亲即可统计好答案。

把问题的求解分为两个部分。同时为了简化讨论,默认以原树的某个重心为根。

子树内

把树重剖一下。

首先,叶子的重心肯定是他自己;从重链往上爬,容易知道其重心也会随着节点的上移而上移。暴力的把重儿子的重心向上调整即可,总复杂度 $O(n)$(因为每个重心都是在对应的重链上爬,路径不交)。

子树外

真正需要注意的是这一部分。

仍然考虑到「重心在根节点的重链上」这个结论,显然删除轻儿子子树内的部分点不会使根节点的重链变化。那么预处理出 $g(x)$ 表示若整个树删掉了 $x$ 大小的子树之后,重心会在这个重链的哪个位置;容易知道随着 $x$ 的减小,重心的位置会逐渐上移,直接 $O(n)$ 地处理出 $g$ 后遍历所有轻儿子统计答案即可。

再考虑删去重儿子子树内某一部分。由于以原树重心为根,所以如果删掉 $x$ 大小的子树之后重儿子仍然是重儿子,那么重心肯定是根(不可能删掉一部分之后重心还向该树内部移动)。若删掉之后原本的次重儿子取而代之,那么会变成和上面一样的问题,同样对次重儿子预处理出 $g$ 求答案。

总复杂度 $O(n)$,注意要时刻判断另一个重心的存在。

另一种思路

以上思路都是基于「考虑删掉一个子树,重心会如何变化」的;实际上也可以考虑「有多少个子树满足删掉之后,剩下的树以我为根」。

同样以重心为根。设删去的子树大小为 $S$,考虑一个非根节点 $u$ 作为重心时是什么情况:
$$
s _u \ge \lceil \frac {n - S} 2 \rceil, s _{son(u)} \le \lfloor \frac {n - S} 2 \rfloor \\
\Rightarrow n - 2 s _u \le S \le n - 2 s _{son(u)}
$$
实际上漏了一个额外条件:删除的点不能位于其子树内。所以先做一遍全局的,统计出有多少个满足条件的 $S$;再 DFS 一遍,访问到一个节点时记录一个值,遍历完子树之后再用现在值减去之前的值,即可得到子树内的影响,用全局值减去即可。

再考虑根。这里的不同是删去重儿子的部分子树时重儿子可能变化,所以分重儿子和轻儿子求解即可。

用树状数组维护上述过程,复杂度 $O(n \log n)$。