牛客练习赛 137 A-G

~~明面上的内测唯一 AK 验题人~~

题目意料之中的难了，但是有点出乎意料过难了。

原本没有这个 B，出题人原本打算弱化现在的 C 放过 nm 加一个只输出删去边集大小的版本做 C（~~这个好像也是我的建议~~），在我建议下增加了输出方案做 B，然后现在的 C 不做弱化。

B 倒是合适了。

但是 CDEFG 好像还是难了，

个人评价：

整场来看是偏典的题，没有比较思维的题，相对最思维的可能就是 D 了，整体码量较高，实现难度略大。

A 抽象题，不做评价。
B 后加的题，感觉是周赛 D 这个位置题。
C“自认为”严格不弱于周赛 71 round F（然后这题 clist 参考是牛客 2100）单独看，放 C 难了。（但是和后面的题整体来看还是合适的）
D,E,F “自认为”难度极差不超过 200，不好评价哪个容易，可能会出现，选手擅长哪个就会先过哪个。
G，字符串科技题，考察了字符串相关算法的应用。

A：

题意简化：

输出 $n$ 的全排列题目编号。

解法一：

枚举全排列，用 A,B,C,D 替换 1,2,3,4 即可。

解法二：

事实上题目限制 $n\le 4$ ，而样例给出了 $n=1,3,4$ 的解，所以特判 $n=2$ ，其它复制样例即可。

B：

题意简化：

给定一棵树，删除最少的边使得给定的 $k$ 个点互不连通。

解法：

观察样例，如果注意力强可以得到 $|E|=k-1$ 的结论。

实际上也很好理解， $k$ 个点互不连通，至少 $k$ 个连通块，而反过来 $k$ 个连通块形成一棵树最少加 $k-1$ 条边。

方案构造也很容易，选择 $k$ 个点中任一点做“根”，删除其它点和父节点的连边即可。

C.

题意简化：

每次 $\frac{1}2$ 概率 $a_i=a_i+(a_i \& m)+x$ ，求进行 $k$ 后的序列的期望和。

解法：

首先。求和的期望是可加的，所以独立计算每一个 $a_i$ ，且容易发现 $a_i\&m$ 的结果只和不高于 $m$ 二进制最高位的二进制位有关。

所以 $a_i$ 进行 $k$ 次的期望等价于 $a_i\bmod 2^{\lceil\log_2(m+1)\rceil}$ 的期望，这样的值只有 $O(m)$ 个。

所以预处理每个初值进行 $k$ 次的贡献。

答案即为 $\frac{1}{2^k}\times \sum\limits_{i=1}^k\binom{k}{i}\times \sum\limits_{j=1}^idp_{t,j}$ ，其中 $t$ 是初始值。

$O(n)$ 预处理组合数， $O(1)$ 询问组合数，时间复杂度： $O(mk)$ 。

D.

题意简化：

给定一个排列，求前缀 $\text{mex}$ 和后缀 $\text{mex}$ 和给定序列相同的，字典序比给定序列大的字典序最小排列。

解法：

若 $pre_i\ne pre_{i-1}$ ，则 $a_i=pre_{i-1}$ ， $suf_i$ 同理。

所以可以先根据前后缀 $\text{mex}$ 确定若干个位置的数。

$[0,pre_i)$ 的位置范围是 $[0,i]$ ， $suf_i$ 同理。

所以可以得到剩下数的位置范围区间。

同时，容易发现，数值大的数的位置范围包含数值更小的数的位置范围。

因为 $\text{mex}$ 是递增的。

所以只要最终排列每个数满足其范围区间，即是合法排列。

那么考虑字典序比原排列大的最小排列。

这大概是一个很典的贪心问题。

从后向前，尝试将当前位变大，第一个可以变大的位一定最优。

考虑有解条件：

设当前位可以移动的范围区间是 $[l,r]$ ，当前位是 $i$ 。

那么， $i<r$ ，且 $[i+1,r]$ 中，存在比 $a_i$ 大的元素即有解，这一步可以使用任意区间最值数据结构维护。

因为大数位置范围包含小数位置范围，所以一定可以交换。

最后，考虑后面的数的位置安排。

此时，问题转换成了给定若干个数的区间，求一种填法，使得字典序最小。

使用 set 维护，贪心填当前位置能填的最小数即可。

对于当前位置 $j$ ，因为区间随数增大扩大，所以在 set 中 lower_bound 最小的 $l<j$ 的元素即可。

时间复杂度： $O(n\log n)$ 。

E.

题意简化：

同 B， $k\le 10^6$ 。

解法：

令 $lim=2^{\lceil\log_2(m+1)\rceil}$ ，容易发现， $k$ 次操作过程中， $(a_i\&m)$ 的值，至少关于 $lim$ 成循环节（根据鸽巢原理容易证明）。

所以 $dp_{t,i}$ 最长以 $lim$ 为循环节。

预处理一个循环节的贡献，令 $Dp_{t,i}=\sum\limits_{j=1}^idp_{t,j}$ ，那么 $Dp_{t,i+l\times len}=Dp_{t,i}+l\times tot$ 。

令 $\delta$ 表示循环前的余项，那么最后计算答案时的式子为 $\sum\limits_{i=\delta+1}^{\delta+len}\binom{k}{i}\times Dp_{t,i}+\binom{k}{i+len}\times Dp_{t,i+len}+\binom{k}{i+2\times len}\times Dp_{t,i+2\times len}+\cdots=\sum\limits_{i=\delta+1}^{\delta+len}[\binom{k}{i}+\binom{k}{i+len}+\binom{k}{k+2\times len}+\cdots]\times Dp_{t,i}+[\binom{k}{i+len}+\binom{k}{k+2\times len}\times 2+\cdots]\times tot$

其中， $Dp_{t,i}$ 只有 $O(lim^2)$ 个，对于每组不同的 $\delta, k$ 需要处理 $\sum\binom{k}{i+l\times len},\sum\binom{k}{i+l\times len}\times l$ ，每次预处理暴力计算是 $O(k)$ 的。

事实上，由于每一个循环节内部的数，其循环节是相同的，所以长为 $len$ 的循环节只需要处理一次，而一次处理了 $len$ 个数的循环节。

所以时间复杂度是均摊： $k\sqrt m$ 的，但是似乎循环节长度会满足一定是 $2$ 的整数幂（暂时不会证明）所以时间复杂度是 $k\log m$ 的。

总时间复杂度： $O(m^2+k\log m)$ 。

F：

题意简化；

给定一个序列，求 $\forall x\in[1,\max\{a\}],\gcd(a_i,a_j)=\gcd(a_k,a_l)=x,i\ne j\ne k\ne l$ 。

解法：

把 $a_i$ 放入 $d\mid a_i$ 的集合中考虑，那么问题等价于在每个 $d$ 中找 $\gcd(A_i,A_j)=\gcd(A_k,A_l)=1$ 。

更进一步的，如果能快速找到 $\gcd(A_i,A_j)=1$ ，那么，可以将 $A_i,A_j$ 去掉，然后再找一次，此时容易分讨：

如果找到了 $\gcd(A_k,A_l)=1$ ，那么问题解决。
反之，如果有解，那么一定是 $\gcd(A_i,A_k)=\gcd(A_j,A_l)=1$ ，此时，用 $A_i,A_j$ 暴力去找另外两个数即可。

至此，核心问题是如何找到 $\gcd(A_i,A_j)=1$ 。

若 $\sum\limits_{x=1}^m[\gcd(A_x,A_i)=1]>1$ ，那么 $A_i$ 就存在 $\gcd(A_i,A_j)=1$ ，此时暴力去找即可。

考虑莫比乌斯反演， $\sum\limits_{x=1}^m[\gcd(A_x,A_i)]=\sum\limits_{x=1}^m\sum\limits_{d|\gcd(A_x,A_i)}\mu(d)=\sum\limits_{d\mid A_i}\mu(d)\sum\limits_{x=1}^m[d\mid A_i]$ 。

枚举 $A_x$ 因子，预处理 $\mu(d)$ 贡献即可。

通过枚举倍数，可以做到均摊 $O(n\ln n)$ 处理因子。

因为题目保证了 $a_i$ 互不相同，所以时间复杂度是均摊的。

综上：枚举 $a_i$ 的因子后再枚举 $A_i$ 的因子，时间复杂度为： $O(\sum\limits_{i=1}^n \sum\limits_{j\mid i}d(j))$ ，其中 $d(j)$ 表示 $j$ 的因子数。本地实测仅有 $7\times 10^6$ 。

若通过科技，可以做到预处理后 $O(1)$ 询问 $10^5$ 范围内的 $\gcd$ ，则时间复杂度仅为上式。若朴素求解 $\gcd$ ，时间复杂度： $O(n\ln n\log n+\sum\limits_{i=1}^n \sum\limits_{j\mid i}d(j))$ 。

空间复杂度： $O(n\ln n)$ 。

G.

题意简化：

给定一个字符串，求 $\forall i\in[1,n]$ ，最小的 $j$ 满足翻转 $s[j,i]$ 后， $s'>s$ 。

解法：

$i$ 的答案可以通过 $i-1$ 的答案扩展一个 $s_i$ 得到。

原问题是对于 $i$ 求最小的 $j$ ，从 $j$ 开始和 $i$ 逆序匹配，且向后第一个不匹配的字符满足 $s_j'<s_i'$ 。

等价于，对于 $s[1,i]$ ，求在反串上满足 $s_{i-CS_{i,j}}>rev(s)_{j-CS_{i,j}}$ 的最大 $j$ 。

对反串建 SAM 容易发现，合法的匹配一定是最长的 $CS_{i,j}$ 在 SAM Slink 树上对应的节点及其到根上的若干节点。而对应的 $j$ 就是节点的 endpos。

而在这些节点中，容易发现，只有最长的 $CS_{i,j}$ 对应的节点，其 $rev(s)_{j-CS_{i,j}}$ 是可能在节点表示字符串集合之内的，其祖先节点，若要匹配 $rev(s)_{j-CS_{i,j}}$ ，那一定是小于这段路径上其儿子节点在其末尾多的的第一个字符。

那么这些信息就可以在建出 SAM 后通过 dfs Slink 树预处理。

具体而言，令 $maxn_{x,ch}$ 表示 $x$ 节点在其表示的最长字符串前加一个字符 ch 时的最大 endpos，因为子节点不唯一，但是父节点唯一，所以把预处理信息挂在子节点上， $x$ 的预处理信息即为其父节点加一个 $short(x)$ 的首字母字符的最大 endpos。

对于从 $s_{i-1}$ 的节点更新到 $s_i$ 的节点，笔者只会分讨，暂时好像不知道如何归一化。

具体而言，初始从根开始跳，若当前节点没有 $s_i$ 的后继状态，则不断跳 Slink 树父节点，直到存在大于跳上来的子节点 $short$ 首字母字符的 endpos（这个其实可以预处理标记，但是实际上不标记也无所谓）且存在 $s_i$ 后继状态。

此时，根据笔者的写法和理解，需要分讨：

$len=maxlen_{cur}$ ，其中 $len$ 表示 $i-1$ 存在的最长 $CS_{i,j}$ ， $maxlen_{cur}$ 是当前节点表示的最长字符串长度。
- 若后继节点 $maxlen_{nex}=maxlen_{cur}+1$ ，说明 $nex$ 节点需要让其 $long$ 前一个字符小于 $s_{i-1-len}$ ，根据预处理信息即可获取此节点上合法的最大 endpos。若其 endpos 对于 $i$ 来说是合法（即对应子串确实在 $i$ 左侧，且没有越过 $i$ ），那么就跳过去，否则继续跳 Slink 树父节点。
- 若后继节点 $maxlen_{nex}>maxlen_{cur}+1$ ，说明其前一个字符是确定的，根据 endpos 获取之，和 $s_{i-1-len}$ 比较，若合法，那么就跳过去，否则继续跳 Slink 树父节点。
$len<maxlen_{cur}$ ，那么只需要考虑 endpos 是否合法即可，合法就跳过去，否则继续跳 Slink 树父节点。

对于朴素的 $s_j<s_i,j<i$ 的情况，用一个数组存储所有字符第一次出现的位置即可判断。

时空复杂度： $O(n\sum|c|)$ ，其中 $|c|$ 表示字符集大小。