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

咕咕咕