BZOJ-3439:Kpm的MC密码(Trie+DFS序+主席树)
背景
想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
题意:Trie树上,求某个点的子树的第K大。
思路:建立Trie树,然后跑得dfs序,然后主席树求第k大。
( 注意当Trie树上一个点代表多个串时,怎么去处理dfs序。
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
int ch[maxn][],cnt,in[maxn],out[maxn],times,tot,np;
int Laxt[maxn],Next[maxn],To[maxn],a[maxn],rt[maxn];
char c[maxn];
struct node{
int l,r,sum;
node(){ l=r=sum=;}
node(int ll,int rr,int ss):l(ll),r(rr),sum(ss){}
}s[maxn*];
void add(int u,int v){
Next[++tot]=Laxt[u];
Laxt[u]=tot; To[tot]=v;
}
void insert(int opt)
{
int L=strlen(c+),Now=;
for(int i=L;i>=;i--){
if(!ch[Now][c[i]-'a']) ch[Now][c[i]-'a']=++cnt;
Now=ch[Now][c[i]-'a'];
}
add(Now,opt);
}
void dfs(int u)
{ //Trie树上同一个点可能有多个串,把他们一起排。
int num=times;
for(int i=Laxt[u];i;i=Next[i]) a[++times]=To[i];
for(int i=;i<;i++) if(ch[u][i]) dfs(ch[u][i]);
for(int i=Laxt[u];i;i=Next[i]) in[To[i]]=num,out[To[i]]=times;
}
void modify(int &Now,int pre,int L,int R,int pos)
{
Now=++np; s[Now]=node(s[pre].l,s[pre].r,s[pre].sum+);
if(L==R) return;
int Mid=(L+R)>>;
if(pos<=Mid) modify(s[Now].l,s[pre].l,L,Mid,pos);
else modify(s[Now].r,s[pre].r,Mid+,R,pos);
}
int query(int Now,int pre,int L,int R,int K)
{
if(s[Now].sum-s[pre].sum<K) return -;
if(L==R) return L;
int Mid=(L+R)>>;
if(s[s[Now].l].sum-s[s[pre].l].sum>=K) return query(s[Now].l,s[pre].l,L,Mid,K);
return query(s[Now].r,s[pre].r,Mid+,R,K-(s[s[Now].l].sum-s[s[pre].l].sum));
}
int main()
{
int N,K,i,j;
scanf("%d",&N);
for(i=;i<=N;i++){
scanf("%s",c+);
insert(i);
}
dfs();
for(i=;i<=N;i++){
modify(rt[i],rt[i-],,N,a[i]);
}
for(i=;i<=N;i++){
scanf("%d",&K);
int ans=query(rt[out[i]],rt[in[i]],,N,K);
printf("%d\n",ans);
}
return ;
}
最新文章
- 我常用的那些linux命令
- OpenCV学习笔记(一)——OpenCV3.1.0+VS2015开发环境配置
- java.lang.String类compareTo()返回值解析
- coco2dx c++ HTTP实现
- Catalog Service - 解析微软微服务架构eShopOnContainers(三)
- c#中的委托和c++中的bind/function对比
- 前端学习之jquery/下
- Centos6.5 安装MYSQL 5.5 -5.6.-5.7 一键yum快速安装 ,初始配置
- _pvp_gap_aura
- oj错误之char型超出范围
- Ubuntu下安装LXC手记之centos
- React组件设计(转)
- 寻找 IBatisNet 批量插入(批量复制) 的心路历程
- 20165203《Java程序设计》第五周学习总结
- poll--wait for some event on a file descriptor
- [转]VC++下使用ADO操作数据库
- Redis .net 客户端 分布式锁
- monkey测试===monkeyrunner测试教程(1)
- USB设备驱动总结
- java 图书馆系统 练习