国外的购物网站有哪些,wordpress企业主题制作教程,网络公司经营范围,陵水网站建设装修设计公司Description 背景 想Kpm当年为了防止别人随便进入他的MC#xff0c;给他的PC设了各种奇怪的密码和验证问题#xff08;不要问我他是怎么设的。。。#xff09;#xff0c;于是乎#xff0c;他现在理所当然地忘记了密码#xff0c;只能来解答那些神奇的身份验证问题了。。…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,此时k12那么”cd”的kpm串有”cd”,”abcd”,”bcd”,编号分别为1,2,3其中第2小的编号就是2PS如果你能在相当快的时间里回答完所有n个ki的查询那么你就可以成功帮kpm进入MC啦~~ Input 第一行一个整数 n 表示字符串的数目 接下来第二行到n1行总共n行每行包括一个字符串第i1行的字符串表示编号为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%的数据1n100000,0len300000 HINT Source Kpmcup#0 By Greens 题目求的是后缀那么把串倒过来就变成前缀问题了可以考虑trie树解决。。。 相当于求串的开头到根节点的路径上的k值。。。 那么可以trie树套值域线段树动态开节点就好了,每个点都有一个到根的路径的值域线段树然后查询k值在线段树上跑一跑就可以了 // MADE BY QT666
#includecstdio
#includealgorithm
#includecmath
#includeiostream
#includecstring
using namespace std;
typedef long long ll;
const int N500050;
int n,trie[N][26],tt,sz,rt[N*20],ls[N*20],rs[N*20],sum[N*20],val[N],ed[N];
char s[N];
void ins(int x,int l,int r,int v){if(!x) xsz;if(lr){sum[x];return;}int mid(lr)1;if(vmid) ins(ls[x],l,mid,v);else ins(rs[x],mid1,r,v);sum[x]sum[ls[x]]sum[rs[x]];
}
void insert(int id){int lenstrlen(s1);int x0;for(int ilen;i;i--){if(!trie[x][s[i]-a]) trie[x][s[i]-a]tt;xtrie[x][s[i]-a];ins(rt[x],1,n,id);}ed[id]x;
}
int query(int x,int l,int r,int k){if(lr){return l;}int mid(lr)1;if(sum[ls[x]]k) return query(ls[x],l,mid,k);else return query(rs[x],mid1,r,k-sum[ls[x]]);
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%s,s1);insert(i);}for(int i1;in;i){int k;scanf(%d,k);if(sum[rt[ed[i]]]k) puts(-1);else printf(%d\n,query(rt[ed[i]],1,n,k));}return 0;
} 转载于:https://www.cnblogs.com/qt666/p/7219614.html
