2020-2021:teams:farmer_john:2020暑假精选题目:字符串
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020暑假精选题目:字符串 [2020/09/04 09:20] jjleo ↷ 页面2020-2021:teams:farmer_john:字符串被移动至2020-2021:teams:farmer_john:2020暑假精选题目:字符串 |
2020-2021:teams:farmer_john:2020暑假精选题目:字符串 [2020/09/04 20:55] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 12: | 行 12: | ||
| 同理有$n->2n+2$的变换，，$s=txxuxx,p=tx$，证明同上。\\ | 同理有$n->2n+2$的变换，，$s=txxuxx,p=tx$，证明同上。\\ | ||
| 根据这个变换即可以$n=1$或$n=2$为起点，构造出符合条件的长度为$O(\log n)$的字符串。 | 根据这个变换即可以$n=1$或$n=2$为起点，构造出符合条件的长度为$O(\log n)$的字符串。 | ||
| + | |||
| + | |||
| + | =====CF1393E2===== | ||
| + | |||
| + | ====题意==== | ||
| + | 给出$n$个字符串，对每个字符串，可以删除其任意一个字符或让其保持原样，求最后使得字符串字典序不降的方案数，对$10^9+7$取模。$(1 \le n \le 10^5, \sum|s_i| \le 10^6)$ | ||
| + | |||
| + | |||
| + | ====题解==== | ||
| + | 本题的难点在于对于一个字符串删去至多一个字符后得到的数个字符串的排序问题。设字符串长度为$L$，我们可以利用如下的算法在$O(L)$完成。 | ||
| + | |||
| + | 设第$i$个字符右边第一个与$s_i$不同的字符为$nxt_i$，如果没有令$nxt_i=z$。维护两个指针$l=1,r=L$，从左到右依次考虑每个字符，如果$s_i>nxt_i$，那么删去第$i$个字符后得到的字符串排序后在第$l$个位置，并令$l++$；否则删去第$i$个字符后得到的字符串排序后在第$r$个位置，并令$r--$。原字符串所在位置位于删去最后一个字符所得到字符串的后面。 | ||
| + | |||
| + | 简要证明：如果$s_i>nxt_i$，那么删掉后面的字符都会比删掉这个字符先碰到一个更大的，因此当前字符就是最小的，反之亦然。 | ||
| + | |||
| + | 之后我们可以维护对于每一个字符串排序过后的序列，以每一种结尾的合法序列有多少个，因为我们已经排序过，所以转移时可以利用双指针进行快速转移，我们再写一个稍微特殊一点的哈希用于比较两个至多删去/没删字符串的大小即可。总复杂度$O(L \log L)$，注意string的最后一位并不一定是'\0'，对于长度过长的边界情况，要直接特判。 | ||
| + | |||
2020-2021/teams/farmer_john/2020暑假精选题目/字符串.1599182414.txt.gz · 最后更改: 2020/09/04 09:20 由 jjleo
