牛客练习赛 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：
题意简化：
输出 的全排列题目编号。
解法一：
枚举全排列，用 A,B,C,D 替换 1,2,3,4 即可。
解法二：
事实上题目限制 ，而样例给出了
的解，所以特判
，其它复制样例即可。
B：
题意简化：
给定一棵树，删除最少的边使得给定的 个点互不连通。
解法：
观察样例，如果注意力强可以得到 的结论。
实际上也很好理解， 个点互不连通，至少
个连通块，而反过来
个连通块形成一棵树最少加
条边。
方案构造也很容易，选择 个点中任一点做“根”，删除其它点和父节点的连边即可。
C.
题意简化：
每次 概率
，求进行
后的序列的期望和。
解法：
首先。求和的期望是可加的，所以独立计算每一个 ，且容易发现
的结果只和不高于
二进制最高位的二进制位有关。
所以 进行
次的期望等价于
的期望，这样的值只有
个。
所以预处理每个初值进行 次的贡献。
答案即为 ，其中
是初始值。
预处理组合数，
询问组合数，时间复杂度：
。
D.
题意简化：
给定一个排列，求前缀 和后缀
和给定序列相同的，字典序比给定序列大的字典序最小排列。
解法：
若
，则
，
同理。
所以可以先根据前后缀 确定若干个位置的数。
的位置范围是
，
所以可以得到剩下数的位置范围区间。
同时，容易发现，数值大的数的位置范围包含数值更小的数的位置范围。
因为 是递增的。
所以只要最终排列每个数满足其范围区间，即是合法排列。
那么考虑字典序比原排列大的最小排列。
这大概是一个很典的贪心问题。
从后向前，尝试将当前位变大，第一个可以变大的位一定最优。
考虑有解条件：
设当前位可以移动的范围区间是 ，当前位是
。
那么，，且
中，存在比
大的元素即有解，这一步可以使用任意区间最值数据结构维护。
因为大数位置范围包含小数位置范围，所以一定可以交换。
最后，考虑后面的数的位置安排。
此时，问题转换成了给定若干个数的区间，求一种填法，使得字典序最小。
使用 set 维护，贪心填当前位置能填的最小数即可。
对于当前位置 ，因为区间随数增大扩大，所以在
set 中 lower_bound 最小的 的元素即可。
时间复杂度：。
E.
题意简化：
同 B，。
解法：
令 ，容易发现，
次操作过程中，
的值，至少关于
成循环节（根据鸽巢原理容易证明）。
所以 最长以
为循环节。
预处理一个循环节的贡献，令 ，那么
。
令 表示循环前的余项，那么最后计算答案时的式子为
其中， 只有
个，对于每组不同的
需要处理
，每次预处理暴力计算是
的。
事实上，由于每一个循环节内部的数，其循环节是相同的，所以长为 的循环节只需要处理一次，而一次处理了
个数的循环节。
所以时间复杂度是均摊： 的，但是似乎循环节长度会满足一定是
的整数幂（暂时不会证明）所以时间复杂度是
的。
总时间复杂度：。
F：
题意简化；
给定一个序列，求 。
解法：
把 放入
的集合中考虑，那么问题等价于在每个
中找
。
更进一步的，如果能快速找到 ，那么，可以将
去掉，然后再找一次，此时容易分讨：
- 如果找到了
，那么问题解决。
- 反之，如果有解，那么一定是
，此时，用
暴力去找另外两个数即可。
至此，核心问题是如何找到 。
若 ，那么
就存在
，此时暴力去找即可。
考虑莫比乌斯反演，。
枚举 因子，预处理
贡献即可。
通过枚举倍数，可以做到均摊 处理因子。
因为题目保证了 互不相同，所以时间复杂度是均摊的。
综上：枚举 的因子后再枚举
的因子，时间复杂度为：
，其中
表示
的因子数。本地实测仅有
。
若通过科技，可以做到预处理后 询问
范围内的
，则时间复杂度仅为上式。若朴素求解
，时间复杂度：
。
空间复杂度：。
G.
题意简化：
给定一个字符串，求 ，最小的
满足翻转
后，
。
解法：
的答案可以通过
的答案扩展一个
得到。
原问题是对于 求最小的
，从
开始和
逆序匹配，且向后第一个不匹配的字符满足
。
等价于，对于 ，求在反串上满足
的最大
。
对反串建 SAM 容易发现，合法的匹配一定是最长的 在 SAM Slink 树上对应的节点及其到根上的若干节点。而对应的
就是节点的 endpos。
而在这些节点中，容易发现，只有最长的 对应的节点，其
是可能在节点表示字符串集合之内的，其祖先节点，若要匹配
，那一定是小于这段路径上其儿子节点在其末尾多的的第一个字符。
那么这些信息就可以在建出 SAM 后通过 dfs Slink 树预处理。
具体而言，令 表示
节点在其表示的最长字符串前加一个字符
ch 时的最大 endpos，因为子节点不唯一，但是父节点唯一，所以把预处理信息挂在子节点上， 的预处理信息即为其父节点加一个
的首字母字符的最大 endpos。
对于从 的节点更新到
的节点，笔者只会分讨，暂时好像不知道如何归一化。
具体而言，初始从根开始跳，若当前节点没有 的后继状态，则不断跳 Slink 树父节点，直到存在大于跳上来的子节点
首字母字符的 endpos（这个其实可以预处理标记，但是实际上不标记也无所谓）且存在
后继状态。
此时，根据笔者的写法和理解，需要分讨：
，其中
表示
，
是当前节点表示的最长字符串长度。
- 若后继节点
，说明
节点需要让其
前一个字符小于
，根据预处理信息即可获取此节点上合法的最大 endpos。若其 endpos 对于
- 若后继节点
，说明其前一个字符是确定的，根据 endpos 获取之，和
- 若后继节点
，那么只需要考虑 endpos 是否合法即可，合法就跳过去，否则继续跳 Slink 树父节点。
对于朴素的 的情况，用一个数组存储所有字符第一次出现的位置即可判断。
时空复杂度：，其中
表示字符集大小。
