2020-2021:teams:farmer_john:2020暑假精选题目:字符串
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:2020暑假精选题目:字符串 [2020/09/04 20:51] jjleo [题解] |
2020-2021:teams:farmer_john:2020暑假精选题目:字符串 [2020/09/04 20:55] (当前版本) jjleo [题解] |
||
|---|---|---|---|
| 行 26: | 行 26: | ||
| 简要证明：如果$s_i>nxt_i$，那么删掉后面的字符都会比删掉这个字符先碰到一个更大的，因此当前字符就是最小的，反之亦然。 | 简要证明：如果$s_i>nxt_i$，那么删掉后面的字符都会比删掉这个字符先碰到一个更大的，因此当前字符就是最小的，反之亦然。 | ||
| + | |||
| + | 之后我们可以维护对于每一个字符串排序过后的序列，以每一种结尾的合法序列有多少个，因为我们已经排序过，所以转移时可以利用双指针进行快速转移，我们再写一个稍微特殊一点的哈希用于比较两个至多删去/没删字符串的大小即可。总复杂度$O(L \log L)$，注意string的最后一位并不一定是'\0'，对于长度过长的边界情况，要直接特判。 | ||
2020-2021/teams/farmer_john/2020暑假精选题目/字符串.1599223866.txt.gz · 最后更改: 2020/09/04 20:51 由 jjleo
