JZOJ 4644. 【NOI2016模拟7.16】人生的经验

题目

给定 c , l ,c是字符集的大小,l是”子串”的长度。即”子串”是由l个在字符集中的字符组成的字符串。现需要求一个字符串,是的这个字符串包含所有的”子串”且长度最小。

解题思路

可以证明,答案必为 c l + l 1
证明:
建立 c l 1 个节点,每个节点代表“子串”的前缀。
则每个”子串”是这样表示的:该“子串”的前缀向后缀连一条标记为该“子串”最后一个字母的边。
比如: a a b 表示为 a a a b ,这条边的标记为 b
意义:接上 b 后,原来的前缀 a a 变成了现在的前缀 a b
恰好,每个节点的入度和出度都为 c 。显然,这是有欧拉回路的。
但是点数很多啊。
没问题,这题的图比较特殊,只用存每个[“子串”的前缀]的标号即可。
圈套圈算法求欧拉回路:
选一个点为起点,在图上乱走。假设走到死胡同了,此时在点a,往后退到点b,并存下走向死胡同的边。这条边是确定了方向的。再从b开始乱走,当又走回b时,相当于获得了一个更大的环。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 10485770
#define P(a) putchar(a)
#define fo(i,a,b) for(i=a;i<=b;i++)
using namespace std;
int i,j,k,c,l,n,m,ans;
int mo,gs,top;
char st[30],a[30],s[N],s1[N];
bool bz[N];
int St[N],E[N];
void dg(){
    int i,p,x,z;
    top=1;
    St[top]=0;
    while(top){
        p=0;
        x=St[top];
        for(i=E[x];i<c;i++){
            z=x+i;
            if(!bz[z]){
                bz[z]=1;
                p=1;
                E[x]=i+1;
                St[++top]=(z%mo)*c;
                s1[top]=st[i];
                break;
            }
        }
        if(!p){
            if(top>1)
            s[++gs]=s1[top];
            top--;
        }
    }
}
int main(){
    freopen("life.in","r",stdin);
    freopen("life.out","w",stdout);
    scanf("%d%d\n",&c,&l);
    scanf("%s",st);
    ans=1;
    fo(i,1,l)ans=ans*c;ans+=l-1;
    mo=1;
    fo(i,1,l-1)mo=mo*c;
    printf("%d\n",ans);
    dg();
    fo(i,1,gs)P(s[i]);
    fo(i,1,l-1)P(st[0]);
    return 0;
}
相关文章
相关标签/搜索