ABC200 题解
[toc]
AC代码
A – Century
B – 200th ABC-200
C – Ringo’s Favorite Numbers 2
D – Happy Birthday! 2
给定一个大小为 $N$ 的数组 $A$ ，找出两个长度分别为 $x,y$ 的递增序列 $B,C$ 使得：
$$
\begin{aligned}
\sum_{i=1}^x A_{B_i}\equiv \sum_{i=1}^y A_{C_i}\equiv \pmod{200}
\end{aligned}
$$
并且 $B$ 和 $C$ 至少存在一个长度 $\leq\min(x,y)$ 的前缀不同。$N\leq 200$ 。
用 $dp[i][j]$ 表示数组 $A$ 前 $i$ 个数选了能否表示出 $j$ （模200意义下）。那么就有一个 $n^2$ 的转移：
$$
\begin{aligned}
dp[i][(j+a[i])\%200]=dp[i-1][j]
\end{aligned}
$$
初值是 $dp[0][0]=1$ 。然后思考如何得到序列 $B,C$ ，这只需要对于每一个合法的 $j$ 暴力存储状态，这最多只有200个。比如 $dp[i-1][j]$ 存在一个合法序列 $s_0,\cdots,s_m$ ，那么 $dp[i][(j+a[i])$ 就记录一个合法序列 $s_0,\cdots,s_m,a[i]$ 。只要得到一对存在一个长度 $\leq\min(x,y)$ 的前缀不同的序列 $B,C$ 就得到了答案，总体复杂度 $O(N^3)$ 。
E – Patisserie ABC 2
有 $N^3$ 个三元组 $(i,j,k)$ 满足 $i,j,k\in(1,2,\cdots,n)$ 。现在按以下方案排序：
- 第一关键字为 $i+j+k$ ;
- 第二关键字为 $i$ ;
- 第三关键字为 $j$ 。
询问序列中第 $K$ 个三元组是什么？
$N\leq 10^6, K\leq N^3$ 。
如果我们知道这个三元组 $i+j+k$ 的值那么这个问题可以直接 $O(N)$ 枚举 $i$ 解决，于是关键就是如果得到 $i+j+k=s$ 的不同三元组个数。
这个问题有一个dp的想法：设 $dp[i][j]$ 表示前 $i$ 个数和为 $j$ 的方案数，那么 $dp[i][j]$ 就能转移到 $dp[i+1][j+1],dp[i+1][j+2],\cdots,dp[i+1][j+n]$ 。直接转移的话复杂度是 $O(3n^2)$ ，但是可以通过前缀和或者数据结构优化掉一个 $N$ 。
F – Minflip Summation
将一个由
0, 1, ?构成的字符串 $s$ 复制 $k$ 份连接起来。每个?既可以是1，也可以是0，因此一共有 $2^{kq}$ 个不同的字符串（$q$ 代表字符串 $s$ 中?的数量）。对于每种不同的字符串，询问最少需要翻转几次区间才能将字符串中的所有字符变成完全一致的，对于所有不同的字符串求和。翻转区间 $[l,r]$ 指的是将 $s_ls_{l+1}\ldots s_r$ 中的
1翻转为0，0翻转为1。$|s|\leq 10^5,k\leq 10^9$ 。
先解决一个最简单的子问题：不考虑 ? 字符，一个只含有 0, 1 的字符串最少需要翻转几次？手模一下不难发现是 $\lceil\frac{dif}{2}\rceil$ ，$dif$ 指的是字符串 $s$ 中发生变化的字符对 $(s_i,s_{i+1})$ 的数量，也就是说 $s_i\neq s_{i+1}$ 的数量。证明仍然不会。
这个式子中由于有一个向上取整符号，计算非常麻烦，因此我们考虑能否消掉这个取整符号。不难发现，如果需要向上取整，那这个字符串的首字符 $s_0$ 一定不等于尾字符 $s_{n-1}$ ，如果不需要向上取整，那这个字符串的首字符 $s_0$ 一定等于尾字符 $s_{n-1}$ ，这意味着我们可以把字符串给看作一个环！这样的话，$dif$ 一定就是一个偶数，除以二不需要向上取整了。而且这个操作对于复制了 $k$ 份的字符串仍然成立，因此我们解决了不含 ? 时的子问题。
加入 ? 字符后，考虑利用期望的思想解决问题：
上文子问题的解决方案中，关键在于不等的字符对 $(s_i,s_{i+1})$ 的数量 $dif$ ，加入 ? 后，可以从期望的角度考虑此时的不等字符对 $(s_i,s_{i+1})$ 的数量该如何计算，有以下几种情况：
s[i] = s[i+1] && s[i], s[i+1] != ?：这时显然没有不等字符对；s[i] != s[i+1] && s[i], s[i+1] != ?：这时显然一定会产生一对不等字符对；s[i] = ?：分类讨论一下不难发现，不论s[i+1]是什么字符，都有 $0.5$ 的概率产生一对不等字符对；s[i+1] = ?：分类讨论一下不难发现，不论s[i]是什么字符，都有 $0.5$ 的概率产生一对不等字符对；
由于任意两个相邻字符对之间的取值是相互独立的，所以每一对相邻字符对答案的贡献是 $p\times 2^{kq}\times k$ ，其中 $p$ 表示产生不等字符对的概率；因此，我们可以在 $O(|s|)$ 的时间复杂度内解决本题。
最后注意特判一个特例：s = ?, k = 1 就解出了本题。