BZOJ 3439: Kpm的MC密码

正文索引 [隐藏]

Description
Input
Output
Sample Input
Sample Output
题解

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

题解

我们建一颗Tire树，把每个字符串倒过来插在上面。每一个点都建一颗主席树，对于每个询问，爬到相应节点上，在主席树上二分答案。

//WNJXYK
//while(true) RP++;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int n;
int ind;
char rstr[300010];
char str[300010];
int len;
int cx[100010];
struct Btree{
    int lx,rx;
    int siz;
};
Btree tree[300010*10];
int nume;
void insert(int &x,int left,int right,int pos){
    if (!x){
        x=++nume;
        tree[x].lx=tree[x].rx=0;
        tree[x].siz=0;
    }
    tree[x].siz++;
    if (left==right){
    }else{
        int mid=(left+right)/2;
        if (pos<=mid) insert(tree[x].lx,left,mid,pos);
        if (mid+1<=pos) insert(tree[x].rx,mid+1,right,pos);
    }
}
int Root;
struct Ttree{
    int ch[26];
    int Root;
};
Ttree tire[300010];
int tnume;
void insertTire(int &x,int now){
    if (!x){
        x=++tnume;
        memset(tire[x].ch,0,sizeof(tire[x].ch));
        tire[x].Root=0;
        //printf("New Node %d\n",x);
    }
    insert(tire[x].Root,1,n,ind);
    if (now>=len){
        cx[ind]=x;
        return;
    }
    //printf("Insert Edge %c\n",str[now]);
    insertTire(tire[x].ch[str[now]-'a'],now+1);
}
inline int query(int x,int k){
    int left=1,right=n;
    //int ans=-1;
    if (tree[x].siz<k) return -1;
    while(left<right){
        int lx=tree[x].lx,rx=tree[x].rx;
        int mid=(left+right)/2;
        int rank=tree[lx].siz;
        //printf("Left:%d Right:%d ->Lsize:%d\n",left,right,rank);
        if (k<=rank){
            //ans=mid;
            //printf("Mid:%d\n",mid);
            right=mid;
            x=lx;
        }else{
            k-=rank;
            left=mid+1;
            x=rx;
        }
    }
    return left;
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++){
        ind=i;
        scanf("%s",rstr);
        len=strlen(rstr);
        for (int i=0;i<len;i++)
            str[len-1-i]=rstr[i];
        //printf("Insert %s\n",str);
        insertTire(Root,0);
    }
    for (int i=1;i<=n;i++){
        int k;
        scanf("%d",&k);
        int rt=tire[cx[i]].Root;
        printf("%d\n",query(rt,k));
    }
    return 0;
}

//WNJXYK

//while(true) RP++;

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<string>

#include<cstring>

using namespace std;

int n;

int ind;

char rstr[300010];

char str[300010];

int len;

int cx[100010];

struct Btree{

int lx,rx;

int siz;

};

Btree tree[300010*10];

int nume;

void insert(int &x,int left,int right,int pos){

if (!x){

x=++nume;

tree[x].lx=tree[x].rx=0;

tree[x].siz=0;

}

tree[x].siz++;

if (left==right){

}else{

int mid=(left+right)/2;

if (pos<=mid) insert(tree[x].lx,left,mid,pos);

if (mid+1<=pos) insert(tree[x].rx,mid+1,right,pos);

}

int Root;

struct Ttree{

int ch[26];

int Root;

};

Ttree tire[300010];

int tnume;

void insertTire(int &x,int now){

if (!x){

x=++tnume;

memset(tire[x].ch,0,sizeof(tire[x].ch));

tire[x].Root=0;

//printf("New Node %d\n",x);

}

insert(tire[x].Root,1,n,ind);

if (now>=len){

cx[ind]=x;

return;

}

//printf("Insert Edge %c\n",str[now]);

insertTire(tire[x].ch[str[now]-'a'],now+1);

}

inline int query(int x,int k){

int left=1,right=n;

//int ans=-1;

if (tree[x].siz<k) return -1;

while(left<right){

int lx=tree[x].lx,rx=tree[x].rx;

int mid=(left+right)/2;

int rank=tree[lx].siz;

//printf("Left:%d Right:%d ->Lsize:%d\n",left,right,rank);

if (k<=rank){

//ans=mid;

//printf("Mid:%d\n",mid);

right=mid;

x=lx;

}else{

k-=rank;

left=mid+1;

x=rx;

}

return left;

}

int main(){

//freopen(".in","r",stdin);

//freopen(".out","w",stdout);

scanf("%d",&n);

for (int i=1;i<=n;i++){

ind=i;

scanf("%s",rstr);

len=strlen(rstr);

for (int i=0;i<len;i++)

str[len-1-i]=rstr[i];

//printf("Insert %s\n",str);

insertTire(Root,0);

}

for (int i=1;i<=n;i++){

int k;

scanf("%d",&k);

int rt=tire[cx[i]].Root;

printf("%d\n",query(rt,k));

}

return 0;

}

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

WNJXYKの博客

喂你脚下有坑