[bzoj3998]弦论

概述建立后缀自动机，对于一个节点，根据len排序后依次统计（t为0时每一个点只有1的贡献，t为1时每个点有|right|的贡献）子树内的子串数量，然后不断确定字符即可。 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 int V,last,k,sum,a[N<<1],sz[N<<1],id[N<<

建立后缀自动机，对于一个节点，根据len排序后依次统计（t为0时每一个点只有1的贡献，t为1时每个点有|right|的贡献）子树内的子串数量，然后不断确定字符即可。

 1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 500005 4 int V,last,k,sum,a[N<<1],sz[N<<1],ID[N<<1],ans[N<<1],len[N<<1],fa[N<<1],ch[N<<1][31]; 5 char s[N]; 6 voID add(int c){ 7     int p=last,np=last=++V; 8     len[np]=len[p]+1; 9     sz[np]=1;10     for(;(p)&&(!ch[p][c]);p=fa[p])ch[p][c]=V;11     if (!p)fa[np]=1;12     else{13         int q=ch[p][c];14         if (len[q]==len[p]+1)fa[np]=q;15         else{16             int nq=++V;17             len[nq]=len[p]+1;18             memcpy(ch[nq],ch[q],sizeof(ch[q]));19             fa[nq]=fa[q];20             fa[q]=fa[np]=nq;21             for(;(p)&&(ch[p][c]==q);p=fa[p])ch[p][c]=nq;22         }23     }24 }25 int main(){26     int t,k;27     scanf("%s%d%d",s,&t,&k);28     V=last=1;29     for(int i=0;s[i];i++)add(s[i]-‘a‘);30     for(int i=1;i<=V;i++)a[len[i]]++;31     for(int i=1;s[i-1];i++)a[i]+=a[i-1];32     for(int i=V;i;i--)ID[a[len[i]]--]=i;33     for(int i=V;i;i--)sz[fa[ID[i]]]+=sz[ID[i]];34     if (!t)35         for(int i=1;i<=V;i++)sz[i]=1;36     memcpy(a,sz,sizeof(a));37     sz[0]=a[0]=sz[1]=0;38     for(int i=V;i;i--)39         for(int j=0;j<26;j++)a[ID[i]]+=a[ch[ID[i]][j]];40     if (a[1]<k){41         printf("-1");42         return 0;43     }44     for(int i=1;k>0;k-=sz[i])45         for(int j=0;j<26;j++)46             if (k>a[ch[i][j]])k-=a[ch[i][j]];47             else{48                 printf("%c",j+‘a‘);49                 i=ch[i][j];50                 break;51             }52 }

VIEw Code 总结

以上是内存溢出为你收集整理的[bzoj3998]弦论全部内容，希望文章能够帮你解决[bzoj3998]弦论所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。