BZOJ3439: Kpm的MC密码

3439: Kpm的MC密码

Time Limit: 15 Sec Memory Limit: 256 MB
Submit: 166 Solved: 79
[Submit][Status]

Description

背景

想Kpm当年为了防止别人随便进入他的MC，给他的PC设了各种奇怪的密码和验证问题（不要问我他是怎么设的。。。），于是乎，他现在理所当然地忘记了密码，只能来解答那些神奇的身份验证问题了。。。

描述

Kpm当年设下的问题是这样的：

现在定义这么一个概念，如果字符串s是字符串c的一个后缀，那么我们称c是s的一个kpm串。

系统将随机生成n个由a…z组成的字符串，由1…n编号（s1,s2…,sn），然后将它们按序告诉你，接下来会给你n个数字，分别为k1…kn，对于每一个ki，要求你求出列出的n个字符串中所有是si的kpm串的字符串的编号中第ki小的数，如果不存在第ki小的数，则用-1代替。（比如说给出的字符串是cd,abcd,bcd,此时k1=2，那么”cd”的kpm串有”cd”,”abcd”,”bcd”,编号分别为1,2,3其中第2小的编号就是2）（PS：如果你能在相当快的时间里回答完所有n个ki的查询，那么你就可以成功帮kpm进入MC啦~~）

Input

第一行一个整数 n 表示字符串的数目

接下来第二行到n+1行总共n行，每行包括一个字符串，第i+1行的字符串表示编号为i的字符串

接下来包括n行，每行包括一个整数ki，意义如上题所示

Output

包括n行，第i行包括一个整数，表示所有是si的kpm串的字符串的编号中第ki小的数

Sample Input

3
cd
abcd
bcd
2
3
1

Sample Output

2
-1
2

样例解释

“cd”的kpm 串有”cd”,”abcd”,”bcd”,编号为1,2,3，第2小的编号是

2，”abcd”的kpm串只有一个，所以第3小的编号不存在，”bcd”的kpm

串有”abcd”,”bcd”,第1小的编号就是2。

数据范围与约定

设所有字符串的总长度为len

对于100%的数据，1<=n<=100000,0<len<=300000

HINT

Source

Kpmcup#0 By Greens

题解：

真是一道好题！

很容易想到把字符串反转之后插入一棵trie树，然后s的kpm串就是它的子树，然后dfs序处理一下把子树内的信息变成连续的就可以用主席树求第k小了。

刚开始把kpm串的定义看反了，然后就把每个点到根节点的主席树建了出来。。。

实现的时候有很多细节，我参考了某大牛的代码

代码：

 #include<cstdio>

 #include<cstdlib>

 #include<iostream>

 #include<algorithm>

 #include<cstring>

 #include<queue>

 #include<vector>

 #include<map>

 #include<set>

 #include<stack>

 #include<string>

 #include<cmath>

 #include<cctype>

 using namespace std;

 const int maxlongint=;

 const int inf=;

 int trie[][],o=,fa[];

 vector<int> en[];

 int nx[];

 char a[];

 int root[];

 int lch[],rch[],num[],x=;

 int dfn[][],now=,n;

 int insert(int i,int l,int r,int j)

 {

     x++;

     int t=x;

     lch[t]=lch[i];

     rch[t]=rch[i];

     num[t]=num[i]+;

     if(l!=r)

     {

         int mid=(l+r)>>;

         if(j>mid)

             rch[t]=insert(rch[i],mid+,r,j);

         else

             lch[t]=insert(lch[i],l,mid,j);

     }

     return t;

 }

 int dfs(int i)

 {

     int n1;

     now++;

     int sz=en[i].size(),rt=root[now-];

     for(n1=;n1<sz;n1++)

         rt=insert(rt,,n,en[i][n1]);

     root[now]=rt;

     dfn[i][]=now;

     for(n1=;n1<;n1++)

         if(trie[i][n1])

             dfs(trie[i][n1]);

     now++;

     dfn[i][]=now;

     root[now]=root[now-];

 }

 int get(int i,int j,int k)

 {

     i=root[i-],j=root[j];

     if(num[j]-num[i]<k)

         return -;

     int l=,r=n;

     while(l!=r)

     {

         int mid=(l+r)>>;

         if(num[lch[j]]-num[lch[i]]>=k)

         {

             r=mid;

             i=lch[i];

             j=lch[j];

         }

         else

         {

             k-=num[lch[j]]-num[lch[i]];

             l=mid+;

             i=rch[i];

             j=rch[j];

         }

     }

     return l;

 }

 int main()

 {

     int n1,n2;

     cin>>n;

     for(n1=;n1<=n;n1++)

     {

         scanf("%s",a);

         int len=strlen(a);

         for(n2=;n2<=(len-)/;n2++)

             swap(a[n2],a[len-n2-]);

         int p=;

         for(n2=;n2<len;n2++)

         {

             if(trie[p][a[n2]-]==)

             {

                 o++;

                 trie[p][a[n2]-]=o;

                 fa[o]=p;

             }

             p=trie[p][a[n2]-];

             if(n2==len-)

             {

                 nx[n1]=p;

                 en[p].push_back(n1);

             }

         }

     }

     dfs();

     int t1;

     for(n1=;n1<=n;n1++)

     {

         scanf("%d",&t1);

         printf("%d\n",get(dfn[nx[n1]][],dfn[nx[n1]][],t1));

     }

 }

我的：TLE

 #include<cstdio>

 #include<cstdlib>

 #include<cmath>

 #include<cstring>

 #include<algorithm>

 #include<iostream>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<string>

 #define inf 1000000000

 #define maxn 1000000+5

 #define maxm 5000000

 #define eps 1e-10

 #define ll long long

 #define pa pair<int,int>

 #define for0(i,n) for(int i=0;i<=(n);i++)

 #define for1(i,n) for(int i=1;i<=(n);i++)

 #define for2(i,x,y) for(int i=(x);i<=(y);i++)

 #define for3(i,x,y) for(int i=(x);i>=(y);i--)

 #define mod 1000000007

 using namespace std;

 inline int read()

 {

     int x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}

     return x*f;

 }

 int n,m,cnt=,tot,now,s[maxm],ls[maxm],rs[maxm],t[maxn][],rt[maxn],dfn[maxn][],p[maxn];

 vector<int>G[maxn];

 char st[maxn];

 void update(int l,int r,int x,int &y,int z)

 {

     y=++tot;

     s[y]=s[x]+;

     if(l==r)return;

     ls[y]=ls[x];rs[y]=rs[x];

     int mid=(l+r)>>;

     if(z<=mid)update(l,mid,ls[x],ls[y],z);else update(mid+,r,rs[x],rs[y],z);

 }

 void dfs(int x)

 {

     dfn[x][]=++now;

     int sz=G[x].size(),y=rt[now-],yy=y;

     for0(i,sz-)update(,n,y,yy,G[x][i]),y=yy;

     rt[now]=yy;

     for0(i,)if(t[x][i])dfs(t[x][i]);

     dfn[x][]=++now;

     rt[now]=rt[now-];

 }

 int query(int x,int y,int k)

 {

     int l=,r=n,xx=rt[x-],yy=rt[y];

     if(s[yy]-s[xx]<k)return -;

     while(l!=r)

     {

         int mid=(l+r)>>;

         if(s[ls[yy]]-s[ls[xx]]>=k){xx=ls[xx];yy=ls[yy];r=mid;}

         else {k-=s[ls[yy]]-s[ls[xx]];xx=rs[xx];yy=rs[yy];l=mid+;}

     }

     return l;

 }

 int main()

 {

     freopen("input.txt","r",stdin);

     freopen("output.txt","w",stdout);

     n=read();

     for1(i,n)

     {

         memset(st,,sizeof(st));

         scanf("%s",st+);m=strlen(st+);

         now=;

         for3(j,m,)

         {

             int x=st[j]-'a';

             if(!t[now][x])t[now][x]=++cnt;

             now=t[now][x];

         }

         p[i]=now;G[now].push_back(i);

     }

     now=;

     dfs();

     for1(i,n)

     {

         int k=read();

         printf("%d\n",query(dfn[p[i]][],dfn[p[i]][],k));

     }

     return ;

 }

巴特西