CF723 题解

[toc]

AC代码

A. Mean Inequality

B. I Hate 1111

多组询问，每次询问一个数 $x$ 能否被分解为任意个 $11,111,1111,\ldots$ 的和。

$x\leq 2\times 10^9$ 。

关键是发现 $1111=111\times 10+11$ ，因此只有 $11$ 和 $111$ 是有用的，然后猜想 $\geq 11\times 111$ 的数一定有办法构造出来，$<11\times 111$ 的数用一个背包预处理找出来。

upd:这玩意的下界是有定理的，NOIP中就出现过：NOIP2017 提高组小凯的疑惑。定理是：Chicken McNugget Theorem 。

C1. Potions (Easy Version)

C2. Potions (Hard Version)

从 $1,2,3,\ldots$ 一直走到 $n$ ，每个位置上 $i$ 都有一瓶药水，喝下这瓶药水会让你的生命值增加 $a[i]$ ，生命值初始为 $0$ ，且生命值不能为负数，询问最多能喝下多少瓶药水。

$n\leq 2\times 10^5,-10^9\leq a_i\leq 10^9$ 。

求出关于 $a[i]$ 的前缀和数组 $pre[i]$（这个前缀和数组的意义就是每瓶药水都喝，喝完前 $i$ 瓶后的生命值），可以注意到，如果我们不喝某瓶药水 $j$ ，那么 $[j,n]$ 区间内的 $pre[i]$ 需要整体减去 $a[j]$ 。

根据上述转换，我们需要做的就是尽量最小化不喝的药水的数量，使得任意 $i$ 都满足 $pre[i]\geq 0$ 。

从 $i=1$ 一直遍历到 $i=n$ ，如果 $pre[i]<0$ 那就说明我们在区间 $[1,i]$ 之间需要少喝几瓶药水，用优先队列维护已经经过的药水权值，优先不喝权值较小的（只需要考虑负数药水），直到当前节点的点权 $\geq 0$ ，去掉药水后更新区间 $[i,n]$ 即可。

D. Kill Anton

给定一个只含有 $A,N,T,O$ 的字符串 $S$ ，每次你可以交换 $S$ 中任意两个相邻元素。请你构造一个字符串 $T$ ，使得从 $S$ 变换到 $T$ 需要最多次移动。

$|S|\leq 10^5$ 。

在最优策略下，相同字符的相对位置一定是不变的，因此我们只需要最大化不同字符间的逆序对数。

此时，可以发现 $A,N,T,O$ 全部放在一起时答案取到最大值，比如 AAANNNTTTOOO ，因此可以枚举 $A,N,T,O$ 的全排列，求出逆序对数量最大的情况，时间复杂度 $O(24n\log n)$ 。

E. Oolimry and Suffix Array

给定你长度为 $n$ 的字符串 $S$ 的后缀数组，字符集大小为 $k$ ，求合法的字符串 $S$ 的数量。

$n,k\leq2\times 10^5$ 。

本题有一个核心子问题：已知字符串 $S$ 的后缀数组，求合法字符串 $S$ 的最小字符集大小。这个问题的关键点有两个：

如果 $rk[i]<rk[j]<rk[k]$ 并且 $s[i]=s[k]$，那么 $s[i]=s[j]=s[k]$。这个性质表明：如果我们从 $sa$ 数组的角度查看每个后缀的首字母，这些字母是单调不减的。
如果 $rk[i]<rk[j]$，$s[i]$ 能否等于 $s[j]$ 取决于 $s[i+1]$ 和 $s[j+1]$：如果 $rk[i+1]<rk[j+1]$，那么 $s[i]\leq s[j]$；如果 $rk[i+1]>rk[j+1]$，那么 $s[i]<s[j]$ 。因此如果 $s[i]=s[j]$ 就必须满足 $rk[i+1]<rk[j+1]$ 。

根据这两个条件，我们枚举 $i$ ，每次比较 $rk[sa[i]+1]$ 和 $rk[sa[i+1]+1]$ 的大小，如果 $rk[sa[i]+1]>rk[sa[i+1]+1]$ ，就说明 $sa[i]$ 和 $sa[i+1]$ 这两个位置不能相等，答案 $+1$ 。注意 $sa[i]+1$ 不要越界！

那么本题就可以转化为：已知 $0\leq S_0\leq S_1\leq\ldots\leq S_{n-1}<k$ ，并且其中某些特殊的 $j$ 需要满足 $S_{j}<S_{j+1}$（这些 $j$ 可以根据上方子问题的解得到），求合法序列数量。

对这些特殊的 $j$ 进行一下转换： $S_{j+1}=S_{j+1}-1$ 。不是这些特殊位置则不需要变换，那么整个问题就变成了：

$0\leq S_0\leq S_1\leq \ldots \leq S_{n-1}<k-dif$ ，其中 $dif$ 表示 $S$ 的最小字符集大小。这是一个经典问题（CF57C）：令 $T_i=S_i+i+1$ ，那么就有：$0<T_0<T_1<\ldots<k-dif+n+1$ ，答案就是：

$$
\displaystyle{\binom{k-dif+n+1}{n}}
$$