题解：P6939 [ICPC 2017 WF] Tarot Sham Boast

· · 题解

解题心路：

第一眼看题的时候有点疑惑，明明都是独立随机的符号，为什么连续序列的可能性是不一样的呢？

仔细一想发现可能是因为有的连续序列在总序列中出现多次，但是只能算一次。

怎么解决呢？直接容斥硬算肯定不行，可以分析一下性质。

由样例二可以看到，好像含有更多连续重复的符号、首尾相似的序列，其出现可能性更低，毕竟它们可以重叠起来出现在总序列中，增加了重复计算的次数，扣除之后当然概率更低。

这样类似循环节的性质（注意！对于此处的“循环节”而言，不同点在于字符串长度不一定要是循环节的整数倍，比如 abc 也可以是 abcabca 的循环节。）能自然而然地引发联想：是不是循环节越短、越多，连续序列重叠的可能就越大，因而预测的可能性就更低呢？

验证猜想：

我们不妨用程序手模一下：（用 012 表示三个符号）

#include<bits/stdc++.h>
using namespace std;
#define N 531441//3^n
#define M 729//3^m
#define n 12
#define m 6
struct s{
    int num,lm[m];
    int id;
}a[M];
int ln[N][n];
bool cmp(s a,s b){
    if(a.num==b.num){
        return a.id<b.id;
    }
    return a.num>b.num;
}
int main(){
    freopen("x.out","w",stdout);
    for(int i=0;i<N;i++){
        int I=i;
        for(int j=0;j<n;j++){
            ln[i][j]=I%3;
            I/=3;
        }
    }
    for(int i=0;i<M;i++){
        a[i].id=i;
        int I=i;
        for(int j=0;j<m;j++){
            a[i].lm[j]=I%3;
            I/=3;
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            for(int k=0;k+m-1<n;k++){
                bool bbb=1;
                for(int l=0;l<m;l++){
                    if(ln[i][k+l]!=a[j].lm[l]){
                        bbb=0;
                        break;
                    }
                }
                if(bbb){
                    a[j].num++;
                    break;
                }
            }
        }
    }
    sort(a,a+M,cmp);
    for(int i=0;i<M;i++){
        for(int j=0;j<m;j++){
            cout<<a[i].lm[j];
        }
        cout<<' ';
        cout<<a[i].num<<endl;
    }
}

当总序列长度足够大（12 是一个超级大的数），连续序列长度为 6 时，输出节选如下：

如果把各个例子的循环节用 0 补全到六位数，依次便为600000/560000/460000/456000/360000/356000/246000 123456，数字越小，预测可能性越小。

那么如果总序列长度不够大呢？比如为 10？ 结果如下：

100000 405:6
010000 405:56
100010 405:46
001000 404:456
100100 399:36
010010 399:356
101010 378:246
000000 297:123456

出现次数重复了，似乎不是非常适用。

但是考虑到总序列长度为 10 的情况下，两个长度为 6 的连续序列最多只有 4 位重叠，所以长度大于等于 5 的循环节是无用的，因而将其去掉。（留下各个数字都含有的 6 不影响结果，而且便于排序）

100000 405:6
100010 405:46
100100 399:36
101010 378:246
000000 297:12346

好啊，很好啊。

至此我们打通了思路（结论显然正确，严格证明移步其他题解，绝对不是因为本蒟蒻不会证），接下来开始代码实现。

具体算法：

对于循环节的处理，我们利用 KMP 的思路，对每一个连续序列求出失配数组，然后从连续序列的末尾开始不断跳失配。

过程中所得的下标用其长度 len 减去的结果恰好就是我们所需的各个循环节。（注意长度大于 n-len 的循环节不应记录）

一张简易的的原理图：（14\Rightarrow6\Rightarrow3\Rightarrow1 为过程中下标变化） 得到每个连续序列的循环节后，按照

  1. 首位更大
  2. 数量更多
  3. 输入顺序靠前

对其排序即可得到答案。

代码实现：

#include<bits/stdc++.h>
#define N 1000010
#define M 15
#define LEN 100010
using namespace std;
struct STR{
    char s[LEN];
    int id,numc,cyc[LEN];
}s[M];
int n,m,len,len2;
int nex[LEN];
void kmp(int id){
    memset(nex,0,sizeof(nex));
    for(int i=2;i<=len;i++){
        int NEX=nex[i-1];
        while(NEX && s[id].s[NEX+1]!=s[id].s[i]){
            NEX=nex[NEX];
        }
        if(s[id].s[NEX+1]==s[id].s[i])nex[i]=NEX+1;
    }
    int NEX=nex[len];
    while(NEX){
        if(len2-NEX<=n)s[id].cyc[++s[id].numc]=len-NEX;
        NEX=nex[NEX];
    }
    s[id].cyc[++s[id].numc]=len;
}
bool cmp(STR s1,STR s2){
    int len=min(s1.numc,s2.numc);
    for(int i=1;i<=len;i++){
        if(s1.cyc[i]>s2.cyc[i])return 1;
        if(s1.cyc[i]<s2.cyc[i])return 0;
    }
    if(s1.numc>s2.numc)return 1;
    if(s1.numc<s2.numc)return 0;
    return s1.id<s2.id;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%s",s[i].s+1),len=strlen(s[i].s+1),len2=len<<1;
        s[i].id=i;
        kmp(i);
    }
    sort(s+1,s+1+m,cmp);
    for(int i=1;i<=m;i++){
        printf("%s\n",s[i].s+1);
    }
}