代码源挑战赛 Round 59 题解 - 代码源竞赛平台

T1

100%

直接判断字符串中是否出现连续子串 WA。

枚举 $i=1$ 到 $|S|-1$，如果存在 $S_i=\texttt{W},\quad S_{i+1}=\texttt{A}$，则字符串不好，输出 NO。否则输出 YES。

时间复杂度 $O(|S|)$。

T2

100%

根据题意模拟即可。我们每次交换后，重新扫描整个数组，统计满足 $a_i>a_{i+1}$的位置数量即可。

时间复杂度 $O(nq)$。

T3

100%

由于所有 $t_i$ 互不相同，可以将所有的行动按 $t_i$ 升序排序，然后依次处理。

设 $dead_i$ 表示选手 $i$ 被淘汰的时刻，初始为 $-1$。

对于排序后的选手 $i$：

• 若 $dead_i\ne -1$，说明他已经被淘汰，行动取消；
• 否则他成功执行计划，即
  • 若目标 $p_i$ 尚未被淘汰，则令：$dead_{p_i}=t_i$。
  • 否则目标已经出局，不产生额外影响。

时间复杂度 $O(n\log n)$，为排序的复杂度。

T4

100%

对于每次询问，我们考虑维护删除之后剩下的连续段。

原数组中相邻元素的异或贡献为 $a_i\oplus a_{i-1}$，令前缀和为 $pre_i=\sum_{j=2}^{i}(a_j\oplus a_{j-1})$。

于是原数组中一段连续区间 $[l,r]$ 内部的权值为：

$$\sum_{i=l+1}^{r}(a_i\oplus a_{i-1})=pre_r-pre_l$$

注意当 $l=r$ 时，该值为 $0$，公式依然成立。

对于每次查询给出要删除的下标，删除这些位置后，原数组会被切成若干个未删除的区间。

例如删除位置 $b_j$，那么区间可能是：

$$[1,b_1-1],\ [b_1+1,b_2-1],\ \dots,\ [b_m+1,n]$$

其中空段需要忽略。

该如何求出这些剩余的区间？

考虑遍历被删除的下标，令变量 $lastL$ 表示上一个被删除的位置，初始为 $0$。对于某个删除位置 $b_j$，如果 $lastL + 1 \not= b[j]$，说明中间存在非空剩余段 $[lastL+1,\ b_j-1]$，将其放到待处理的区间集合里。再令 $last = b[j]$。 注意遍历结束后，如果 $lastL \not= n$，还要加入最后一段 $[lastL+1,\ n]$。

设我们处理出来的区间为：

$$[l_1,r_1],[l_2,r_2],\dots,[l_c,r_c]$$

那么对于每个区间内的贡献，可以用前缀和数组计算，对于每个区间相连的部分，我们直接按照题目要求处理出对应位置的答案即可。

时间复杂度为 $O(n + \sum m)$。

T5

100%

考虑贡献。

一个 0110 子序列由四个下标组成：

$$i<j<k<l$$

且：

$$S_i=0,\quad S_j=1,\quad S_k=1,\quad S_l=0$$

这个四元组会被多少个连续子串包含？

子串左端点可以从 $1$ 到 $i$，右端点可以从 $l$ 到 $n$，所以贡献次数为：$i(n-l+1)$

因此答案为所有合法四元组的 $i(n-l+1)$ 的和。

考虑动态规划。设：

• $dp_{i,0}$ 表示在前 $i$ 个字符中，所有 0 子序列的首位下标的和。

• $dp_{i,1}$ 表示在前 $i$ 个字符中，所有 01 子序列的首位 0 的下标的和。

• $dp_{i,2}$ 表示在前 $i$ 个字符中，所有 011 子序列的首位 0 的下标的和。

也就是说，$dp$ 数组不统计子序列数量本身，而是统计这些子序列的“第一个 0 的位置和”。

考虑转移：

1. 如果 $s_i = 0$，那么

$$\begin{aligned} & dp[i][0] = dp[i - 1][0] + i \\ & dp[i][1] = dp[i - 1][1] \\ & dp[i][2] = dp[i - 1][2] \end{aligned}$$

于此同时，这一位如果看成上面四个位置的 $l$ （也就是最后一位），那么其对答案的贡献为 $dp[i][2] \times (n - i + 1)$。

2. 如果 $s[i] = 1$，那么

$$\begin{aligned} & dp[i][0] = dp[i - 1][0] \\ & dp[i][1] = dp[i - 1][1] + dp[i - 1][0] \\ & dp[i][2] = dp[i - 1][2] + dp[i - 1][1] \end{aligned}$$

最后输出答案即可。

时间复杂度 $O(n)$。

T6

100%

考虑数位 dp。由于数位 dp 的写法很多，这里简单介绍其中一种。

设输入的上界数字为字符串 $S$，长度为 $n$；目标数字串为 $t$，长度为 $m$，下标从 $0$ 开始。

定义 $dp[i][j]$ 表示当前从高到低还有 $i$ 位没有填数字，且已经填好的前缀与数字串 $t$ 已经匹配了前 $j$ 个字符时，后续任意填写这 $i$ 位，最终能够使 $t$ 成为整个数字串子序列的方案数。

考虑状态转移。枚举下一位填写的数字 $d \;(0\le d\le 9)$：

1. 若当前已经匹配完整，即 $j=m$，那么匹配状态不会再改变：

$$dp[i][m]=\sum_{d=0}^{9} dp[i-1][m]$$

2. 否则，若当前数字 $d$ 等于下一个需要匹配的字符 $t_j$，那么匹配数量增加 $1$；否则匹配数量不变。因此有：

$$dp[i][j]=\sum_{d=0}^{9} dp[i-1][j+[t_j=d]]$$

其中 $[t_j=d]$ 表示如果条件成立则为 $1$，否则为 $0$。

更具体地写为：

接下来考虑如何统计 $1$ 到 $S$ 之间的所有正整数。

答案分成三类统计：

1. 位数小于 $n$ 的正整数；
2. 位数等于 $n$ 且小于 $S$ 的正整数；
3. 数字 $S$ 本身。

第一种情况，我们可以枚举位数以及第一个数字，从而得到对应 $dp$ 值的答案。

第二种情况，我们可以从小到大枚举与 $n$ 相同的前缀和第一个不相同的数字，同时更新前缀所对应的与 $t$ 匹配的个数，从而得到对应 $dp$ 值的答案。

第三种情况，直接特判即可。

T7

100%

为了解决这个问题，我们需要利用有根森林的拓扑序方案数公式：

$$\frac{n!}{\prod_{u=1}^{n} sz_u}$$

其中 $sz_u$ 表示在当前森林中，以 $u$ 为根的子树大小，即从 $u$ 出发沿保留边向下能够到达的点数。

证明

有根树的情况

先考虑一棵以 $u$ 为根的有根树。考虑动态规划。

设 $f_u$ 表示以 $u$ 为根的子树内部的拓扑序数量。

设 $u$ 的儿子为 $v_1,v_2,\dots,v_c$。由于 $u$ 是这些节点的祖先，所以在 $u$ 子树内部的任意合法拓扑序中，$u$ 必须排在第一位。

剩下的 $sz_u-1$ 个位置由各个儿子子树的拓扑序交错组成。因此有：

$$f_u= \binom{sz_u-1}{sz_{v_1},sz_{v_2},\dots,sz_{v_c}} \prod_{i=1}^{c} f_{v_i}$$

即：

$$f_u= \frac{(sz_u-1)!}{\prod_{i=1}^{c} sz_{v_i}!} \prod_{i=1}^{c} f_{v_i}$$

其中系数 $\frac{(sz_u-1)!}{\prod_{i=1}^{c} sz_{v_i}!}$ 的来源可以参考可重集的全排列。

令 $g_u=\frac{f_u}{sz_u!}$，即 $f_u=sz_u!g_u$，代入上面的转移式：

$$sz_u!g_u= \frac{(sz_u-1)!}{\prod_{i=1}^{c} sz_{v_i}!} \prod_{i=1}^{c}(sz_{v_i}!g_{v_i})$$

整理后可得：

$$g_u=\frac{1}{sz_u}\prod_{i=1}^{c}g_{v_i}$$

可以发现，每个节点 $x$ 都会且只会贡献一次因子：

$$\frac1{sz_x}$$

所以：

$$g_u=\prod_{x\in subtree(u)}\frac1{sz_x}$$

于是：

$$f_u= \frac{sz_u!}{\prod_{x\in subtree(u)}sz_x}$$

森林的情况

设森林由若干棵有根树组成，根为：

$$r_1,r_2,\dots,r_k$$

我们只需要设置一个虚拟的“根”，其中儿子为森林里每个有根树的根，即可证明

$$\frac{n!}{\prod_{u=1}^{n} sz_u}$$

---

回到原先的问题，根据题目的要求和上面推导的公式，有

$$\sum_S F(T_S)= \sum_S n!\prod_{u=1}^{n}\frac1{sz_u}$$

由于 $n!$ 与删边方案无关，可以最后统一乘上：

$$ans= n!\sum_S\prod_{u=1}^{n}\frac1{sz_u}$$

因此问题转化为：

对所有保留/删除边方案，求 $\prod\limits_{u=1}^{n}\frac1{sz_u}$ 的总和。

如何计算？考虑动态规划。

对每个节点 $u$，$dp[u][k]$ 表示只考虑原树中 $u$ 的整棵子树，并枚举这棵子树内所有边的保留或删除方案后，满足 $u$ 在当前森林中的保留子树大小为 $k$ 时，所有方案的权值和。

一个方案的权值定义为：

$$\prod_{x\in subtree(u)}\frac1{sz_x}$$

其中 $sz_x$ 是当前删边方案下，节点 $x$ 在森林中的保留子树大小。

注意，$dp[u][k]$ 已经包含了 $u$ 子树中所有节点的 $\frac1{sz_x}$ 。

故最终答案为：

$$n!\sum_{k=1}^{n}dp[1][k]$$

考虑转移。对于节点 $u$ 的某个儿子 $v$。

边 $(u,v)$ 有两种选择：删除或保留。

1. 如果删除这条边，那么 $v$ 所在部分不会并入 $u$ 的保留子树，因此 $u$ 的保留子树大小不变。此时 $v$ 子树内部可以是任意合法删边方案，所以贡献为：

$$sum_v=\sum_{k=1}^{size_v}dp[v][k]$$

2. 如果保留这条边，那么 $v$ 的保留子树会并入 $u$ 的保留子树。若 $v$ 的保留子树大小为 $k$，则 $u$ 的保留子树大小增加 $k$，贡献为 $dp[v][k]$。

上述两个步骤都可以用树上背包的方法计算得到。

不要忘记最后还要乘上节点 $u$ 自己的因子 $\frac{1}{sz}$，以及要预处理逆元。

时间复杂度为 $O(n^2)$。