[CF1975H] 378QAQ and Core Solution

· · 题解

好有趣的一个题！本来在想怎么实现 std 中那个递归做法，然后翻到了一个厉害的提交记录，发现这个题完全可以做线性代码也很好写，所以在这里记录一下。

题目中的 Core 讲的是一个串的最大后缀。这个最大后缀肯定以最大字符（设为 c）结尾，那么假设 c 唯一存在，你直接把这个字符扔到末尾就是最优解了。

但往往 c 存在多个，你可以容易地得到第一个和最后一个都填 c 是最优的，如果第一个不填 c，那么把首个字符丢到第二个 c 前面一定不劣。末尾不填 c 的话，把末尾的字符串扔到最后一个 c 前面同样不劣。

所以最优的字符串结构形如 cs_1cs_2c\dots cs_kc。假设我们已经得知了所有的 s_1,s_2\dots s_k（这些字符串可能为空！），那么我们考虑重排这些字符串使得原串 Core 最小化，这于原问题形式类似，也就是变成了一个子问题。即重排 (cs_1)(cs_2)\dots (cs_k)(c) 这 k+1 个字符串。

值得一提的是，这个子问题的单个字符变成了一个字符串，而字符串之间的大小比较不是直接的字典序比较，真正的比较关系 s_1\prec s_2\iff cs_1cs_2c<cs_2cs_1c，即将 s_i 的末尾塞无限个 \infin 扩充的无穷字符串之间的比较。以及最后一个字符串 (c) 后面跟的是边界，可以认为是跟了一个 -\infin 然后再跟无穷个 \infin。

我们将字符串离散化之后可以递归下去做。现在的问题就变成了如何确定一个能生成最优解的 s_1,s_2\dots s_k？

第一个观察是由于 s_i 内部可以任意排，所以所有的 s_i 都升序最优。进一步地，所有的 s_i 的第一个字符一定取字符集排序后的一个前缀，否则 Core 的第二个字符不在这个前缀中就严格不优了。

设原串有 a 个 c，b 个不是 c。当 b\ge a 的时候你发现空串严格不优，因为 Core 中前两个字符都成了 c 而这是可以避免的。所以 b\ge a 的时候你的最优策略肯定是先用字符集前缀填上所有 s_i 的第一个字符。此时已经不是最大值的 s_i 可以直接扔了！可以简单的调整法证明这个策略的正确性，比较繁琐所以不展开了。这样我们一轮一轮填下去直到所有的不是 c 的字符都填完即得到了最终的 s_i。

精细实现上述做法，由于每次递归规模减半（a>b 时至多递归规模为 a\bmod b，b\ge a 时至多递归规模为 a）所以是 O(n\log n) 的。

我们有更高明的实现！！注意到我们递归做法中经常重复扫一些已经不是最大值的 s_i，我们考虑改成一种类似非递归的形式。

我们维护一个有序的无穷字符串数列（这个无穷字符串的比较同我们上面所讲的比较），一开始所有位置都是单字符（后面跟一堆 \infin）： A=(-\infin,S_1,S_2\dots,S_n)（其中 S 是输入字符串排序后的结果）。

然后我们从左到右扫描这个序列 A，每次将 A_i 拼接到从左往右第一个最大值位置上，然后删去 A_i。直到 A_n 的最后一个非 \infin 字符是 -\infin（不是删得只剩下一个串的时候！）。那么 A_n 去掉带有 -\infin,\infin 的部分就是我们想要的最小 Core 了！

看起来很神秘？但玩一玩可以发现这和上面的递归做法流程完全等价！只是减少了许多不必要的字符串缩减成一个字符和字符串的移动！

这个过程的复杂度是什么呢？观察发现在这个过程中 A 始终保持有序，所以说它第一个最大值的位置 pos 一定是每次加一，直到其大于 n 之后又跳回某一个位置，暴力维护最大值指针，由于有序用哈希判断最大值，复杂度就是 O(n) 的了。

具体讲下这两个做法为什么本质一样：当每次扫到的 A_i 是以 -\infin 结尾的时候意味着完成了一次递归。每一次 pos 指针跳回一个位置时相当于又给当前 s_i 加完了一轮字符。然后更新指针相当于你扔掉了那些不是最大值的 s_i。

My Code:

#include <list>
#include <cstdio>
using namespace std;
const int N=1000003;
const int B=29,P=1000000009;
typedef long long ll;
int n;
char s[N];
int pw[N];
struct node{
    list<int> s;int val;
    node(){}
    node(int c):s(1,c),val(c+1){}
    void operator+=(node &x){
        s.splice(s.end(),x.s);
        val=((ll)val*pw[x.s.size()]+x.val)%P;
    }
}o[N];
int f[N],cnt[27];
void solve(){
    scanf("%d%s",&n,s+1);
    for(int i=1;i<=n;++i) ++cnt[s[i]-96];
    pw[0]=1;
    for(int i=1;i<=n;++i) pw[i]=(ll)pw[i-1]*B%P;
    o[0]=node(0);n=0;
    for(int c=1;c<=26;++c) while(cnt[c]) --cnt[c],o[++n]=node(c);
    int ps=n;
    for(int i=0;i<=n&&o[n].s.back();++i){
        if(ps==n) while(ps>i&&o[ps].val==o[n].val) --ps;
        o[++ps]+=o[i];
    }
    for(int c:o[n].s) if(c) putchar(c+96);
    putchar('\n');
}
int main(){
    int tc;
    scanf("%d",&tc);
    while(tc--) solve();
    return 0;
}