CF721 题解

[toc]

AC代码

A. And Then There Were K

B1. Palindrome Game (easy version)

B2. Palindrome Game (hard version)

多组询问，给定一个长度为 $n$ 的 $01$ 串 $s$ ，Alice和Bob进行游戏，Alice先行动，两人轮流执行以下操作之一：

花费1元，将 $s$ 中的任意一个 $0$ 变为 $1$ 。

当字符串不是回文串时，可以花费 $0$ 元翻转整个字符串，如果前一个人执行了翻转操作，那么后一个人就不能翻转了。

当 $s$ 变为全 $1$ 串时游戏结束，花费较少的人获胜，询问谁必胜或者平局。

$\sum n\leq 10^6$ 。

easy version给我们一个提示：先考虑 $s$ 初始为回文串的情况。

此时，Alice只能够执行操作1，不难发现：回文串长度为奇数，且中心为 $0$ 时Alice可能取胜，否则必败。因为只有该情况下，Alice可以将回文串进行一次变换后仍然形成回文串（翻转中心点），然后不论Bob变化了哪个 $s_i$ ，回文串一定会变成非回文串，Alice就可以将 $s_i$ 的对偶位置 $s_{n-i-1}$ 翻转……直到只剩下两个0时免费翻转回文串回文串使得Bob的花费必定不少于自己。

因此回文串长度为奇数，且中心为 $0$ 时，Alice能否获胜取决于0的数量，只有 $1$ 个 $0$ 时必败，否则必胜。

接下来考虑 $s$ 初始不是回文串的情况，那么有两种可能：Alice一步就可以将 $s$ 变成回文串，这时除非0的个数是2，否则Alice必胜，因为她一定可以对偶地进行变换，直到剩下两个0时先手进行翻转；Alice不能一步将 $s$ 变成回文串，此时Alice必胜，因为她可以先手翻转字符串，而Bob必须进行一次变化，然后Alice再翻转……直到字符串一步就可以变成回文串时，Alice将 $s$ 变成回文的，防止Bob进行翻转，那么Bob一定会花费更多钱。

最后特判一下初始为全1串的情况。

C. Sequence Pair Weight

给定一个大小为 $n$ 的数组 $a_n$ ，求 $a_n$ 中的任意连续区间 $[l,r]$ 中的相同数对个数之和。

$n\leq 10^5$ 。

对于一对相同数对 $(i,j)$ 而言，当区间 $[l,r]$ 满足 $l\leq i\cap j\leq r$ 时它都会产生贡献，因此可以前缀和扫一次+后缀和扫一次，最后累加起来即可。

D. MEX Tree

给出一棵 $n$ 个点的树，点从 $0$ 到 $n – 1$ 编号。定义一条路径的权值是路径上所有点编号的 $mex$ 。对于每个 $0\le i\le$ 求出 $mex $为 $i$ 的路径（路径至少有两个节点）有几条。

$\sum n\leq 2\times 10^5$ 。

本题的关键观察：

如果一条路径的 $mex$ 是 $i$ ，那么这条路径一定包含 $0,1,\ldots,i-1$ 但不包含 $i$ ，这是显然的。
树上的路径一定是一条链，这说明：我们建立一棵以 $0$ 为根节点的有根树，如果某条路径的 $mex>0$ ，这条链的两个端点一定恰好在根节点的两棵子树中（这条链必须跨过根节点）。
假设我们想要找到某条路径的 $mex=i$ ，那么根据观察1，这条路径中必须完全包含 $0,1,\ldots,i-1$ ，如果这些节点构成的子树的叶子节点 $>2$ ，那么这些节点就无法构成一条链，也就是说不存在这种路径。

接下来利用容斥原理解决本题：由于我们想要求出 $mex=i$ 的路径数量，不妨将其转化为 $mex\geq i$ 的路径数量减去 $mex\geq i+1$ 的路径数量，假设 $f_i$ 表示 $mex=i$ 的路径数量，$p_i$ 表示 $mex\geq i$ 的路径数量，那就得到一个等式：$f_i=p_i-p_{i+1}$ ，因此我们只需要求出 $f_0$ 和 $p_i(i=0,1,\ldots,n-1)$ 。

求 $f_0$

这个问题比较容易：只需要求出所有不经过 $0$ 的路径，只要在以 $0$ 为根的树中找到所有以 $0$ 的儿子作为根的子树大小 $size_u(u是0的儿子)$ ，就有：$f_0=\sum\binom{size_u}{2}$ ，同时也可以得到 $p_0=\binom{n}{2}-f_0$ 。

这可以通过一个简单的dfs实现，同时注意记录以每个节点 $u$ 为根的子树大小 $sub_u$ ，父节点 $fa_u$ 。

求 $p_i$
根据前文的分析，我们已经得到每条路径的形态都是跨过根节点的链，因此可以用 $L$ 代表这条链的左端点，$R$ 代表这条链的右端点，初始时 $L=R=0$ 。由于已经求出了 $p_0$ ，因此我们枚举 $i=1,2,\ldots,n-1$ ，每次从节点 $i$ 开始向他的父节点向上跳直到遇到这条链为止，经过的节点打上标记防止重复遍历，那么有三类情况：
1. 父节点是 $L$ 或者 $R$
  
  那么更新这条链的 $L,R$ ，$mex=i$ 的路径数量就是 $sub_L\times sub_R$ 。
2. 节点 $i$ 已经在链的内部
  
  这说明这条链已经含有 $i$ ，$L,R$ 不需要更新，$mex=i$ 的路径数量仍然是 $sub_L\times sub_R$ 。
3. 父节点不是 $L,R$ ，是链内部的节点
  
  这说明不存在 $mex\ge i$ 的路径，跳出枚举。

综上所述，我们可以在 $O(n)$ 的时间复杂度下求出 $p$ 数组，因此不难根据 $p$ 推出 $f$ 。

E. Partition Game

定义数组 $t$ 的权值如下：

$$
\begin{aligned}
cost(t) = \sum_{x \in set(t) } last(x) – first(x)
\end{aligned}
$$

上式的解释：数组 $t$ 中任意一个元素 $x$ 最后一次出现的位置 $last(x)$ 减去首次出现的位置 $first(x)$ 的值求和。

现在给出一个长度为 $n$ 的数组 $a_n$ ，你需要将它切成 $k$ 段，询问每段连续子数组的权值之和的最小值。

$n\leq 35000,k\leq\min(100,n),a_i\leq n$ 。

容易想到一个naive区间dp，假设 $dp[i][j]$ 表示前 $i$ 个数分为 $k$ 段的最小权值，那么显然有：

\begin{aligned} dp[i][j] = \min(dp[k][j-1]+cost(a_{k+1},a_{k+2},\ldots,a_i) \quad (1\leq k<i) \end{aligned}

上式中的 $cost(a_{k+1},a_{k+2},\ldots,a_i)$ 表示数组 $a_{k+1},a_{k+2},\ldots,a_i$ 的权值。如果我们能够 $O(1)$ 计算 $cost(a_{k+1},a_{k+2},\ldots,a_i)$ ，那么上方的转移就是 $O(n^2k)$ 的，但即使如此也会T飞，因此需要线段树加速转移：

容易观察到 $dp[i][j]$ 的值取决于 $dp[1][j-1]+cost(2,i),dp[2][j-1]+cost(3,i),\ldots$ ，我们可以用线段树 $O(\log n)$ 求出这一段区间的最值，然后本题的关键就是加入了一个数 $a_{i+1}$ 到 $dp[i+1][j]$ 时，能否快速更新前面的节点。

加入 $a_{i+1}$ 时，如果它会产生贡献，那就意味着存在 $a_j(j\leq i)$ 满足 $a_{i+1}=a_j$ ，因此我们只需要对于 $[1,a_j-1]$ 加上新产生的贡献 $i+1-j$ 即可 $O(\log n)$ 更新。

综上，先枚举段数 $j$ ，每次枚举 $j$ 时根据前一层的dp值建立线段树，然后进行转移，复杂度 $O(nk\log n)$ 。

一个类似的问题：CF833B。