BZOJ3439Kpm的MC密碼

Trie树/可持久化线段树


  神题啊……搞了我一下午= =(其实第233个提交也是我的)

  我一开始的思路:这个找kpm串的过程,其实就跟在AC自动机上沿fail倒着往下走是差不多的(看当前是哪些点的后缀,如果某个串的后缀是当前串,那它的fail就会指向这里)所以就在fail树上bfs一遍,然后找到所有的编号,排序后输出第k小……

  然后顺利地WA了 QAQ

  只好取膜拜题解……哦原来只要把每个串倒过来,建Trie树的时候,就相当于找当前这个串的子树!

  在子树中统计啊……so easy啦~dfs一遍,把儿子中的编号传给父亲啦~然后就会发现光荣TLE了>_>

  shen me gui!为什么呢?很简单啦,结点那么多,最坏情况下要把n个编号上传n次(比如有10W个相同的串,每个串都为 "aaa....aa"(10W个a))妥妥的TLE了。

  等等……刚刚好像说是子树查询第K大?dfs序不是很好吗!瞬间转成求区间第K大!可持久化线段树!

  ok,终于顺利AC……

BZOJ3439Kpm的MC密碼
BZOJ3439Kpm的MC密碼
  1 /**************************************************************
  2     Problem: 3439
  3     User: Tunix
  4     Language: C++
  5     Result: Accepted
  6     Time:1240 ms
  7     Memory:51688 kb
  8 ****************************************************************/
  9  
 10 //BZOJ 3439
 11 #include<vector>
 12 #include<cstdio>
 13 #include<cstring>
 14 #include<cstdlib>
 15 #include<iostream>
 16 #include<algorithm>
 17 #define rep(i,n) for(int i=0;i<n;++i)
 18 #define F(i,j,n) for(int i=j;i<=n;++i)
 19 #define D(i,j,n) for(int i=j;i>=n;--i)
 20 #define pb push_back
 21 using namespace std;
 22 inline int getint(){
 23     int v=0,sign=1; char ch=getchar();
 24     while(ch<'0'ch>'9'){ if (ch=='-') sign=-1; ch=getchar();}
 25     while(ch>='0'&&ch<='9'){ v=v*10+ch-'0'; ch=getchar();}
 26     return v*sign;
 27 }
 28 const int N=1e5+10,INF=~0u>>2;
 29 typedef long long LL;
 30 /******************tamplate*********************/
 31 struct Trie{
 32     int ch[26],num;
 33     bool sign;
 34 }T[N];
 35 int cnt=0,n,tot,pos[N];
 36 inline int id(char c){return c-'a';}
 37 vector<int>v[N];
 38 void Insert(char *s,int num){
 39     int x=0,y;
 40     D(i,strlen(s)-1,0){
 41         y=id(s[i]);
 42         if (T[x].ch[y]==0)
 43             T[x].ch[y]=++cnt;
 44         x=T[x].ch[y];
 45     }
 46     T[x].sign=1;
 47     v[x].pb(num);
 48     pos[num]=x;
 49 }
 50 int st[N],ed[N],a[N];
 51 void dfs(int x){
 52     st[x]=tot+1;
 53     rep(i,v[x].size()) a[++tot]=v[x][i];
 54     rep(i,26)
 55         if (T[x].ch[i]!=0)
 56             dfs(T[x].ch[i]);
 57     ed[x]=tot;
 58 }
 59 struct Tree{
 60     int cnt,l,r;
 61 }t[N*30];
 62 int root[N],num=0;
 63 #define mid (l+r>>1)
 64 void update(int &o,int l,int r,int pos){
 65     t[++num]=t[o], o=num, ++t[o].cnt;
 66     if (l==r) return;
 67     if (pos<=mid) update(t[o].l,l,mid,pos);
 68     else update(t[o].r,mid+1,r,pos);
 69 }
 70 int query(int i,int j,int rank){
 71     i=root[i]; j=root[j];
 72     int l=1,r=n;
 73     while(l!=r){
 74         if (t[t[j].l].cnt-t[t[i].l].cnt>=rank)
 75             r=mid,i=t[i].l,j=t[j].l;
 76         else{
 77             rank-=t[t[j].l].cnt-t[t[i].l].cnt;
 78             l=mid+1,i=t[i].r,j=t[j].r;
 79         }
 80     }
 81     if (t[j].cnt-t[i].cnt<rank) return -1;
 82     return l;
 83 }
 84 #undef mid
 85 char s[N];
 86 int main(){
 87 #ifndef ONLINE_JUDGE
 88     freopen("3439.in","r",stdin);
 89     freopen("3439.out","w",stdout);
 90 #endif
 91     n=getint();
 92     F(i,1,n){
 93         scanf("%s",s);
 94         Insert(s,i);
 95     }
 96     dfs(0);
 97 #ifdef debug
 98     F(i,1,tot) printf("%d ",a[i]);puts("");
 99     F(i,1,n) printf("%d %d\n",st[pos[i]],ed[pos[i]]);
100 #endif
101     F(i,1,tot){
102         root[i]=root[i-1];
103         update(root[i],1,n,a[i]);
104     }
105 #ifdef debug
106     F(i,1,num) printf("%d %d %d %d\n",i,t[i].l,t[i].r,t[i].cnt);
107 #endif
108     int k;
109     F(i,1,n){
110         k=getint();
         int ans=query(st[pos[i]]-1,ed[pos[i]],k);
112 //      printf("%d\n",ans>n ? -1 : ans);
113         printf("%d\n",ans);
114     }
115     return 0;
116 }
View Code

3439: Kpm的MC密码

Time Limit: 15 Sec  Memory Limit: 256 MB
Submit: 234  Solved: 113
[Submit][Status][Discuss]

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<=100,0

HINT

Source

Kpmcup#0 By Greens

[Submit][Status][Discuss]
更多相关文章
  • BZOJ3439 Kpm的MC密碼
    云神出的题= =,逼得蒟蒻要跳楼了 这道题的话...先把读入的字符串反转,然后建trie树 发现一个字符串的kpm串就是他的结尾字符的子树,于是对所有是字符串结尾的点按照dfs序展成一个序列. 问题转化为求区间第k大,用主席树什么的就好了...   1 /**********************
  • 


    		    SQL SERVER2008 忘記SA密碼怎麼辦
    SQL2008 Instance如果只有一個SA管理帳號,且登入帳號中未加入本機Administrator帳號, 這時SA密碼忘了或Disable是否還有辦法可以重新開啟或修改呢? 還是只能走向重新安裝這條路呢?(這是條不歸路...XD) 這篇記錄如何以系統管理員身分,重新取得SQL Server
  • 493萬Gmail用戶的賬號密碼遭洩露,Google否認自己存在安全漏洞
    最近,大公司在互聯網信息安全問題上狀況頻出.上週,蘋果因iCloud被黑客攻擊而導致大量明星私照外洩,著實是熱鬧了一陣.而Google也來湊熱鬧了.據俄羅斯媒體CNews消息,近493萬Gmail用戶的賬號和密碼被發佈到了俄羅斯的一個比特幣論壇上,所幸暫時還沒有造成更大規模的相關隱私信息洩露.不過,
  • 破解windowsXP,window2000的开机密码 一. 有些刚接解电脑的人,常常对administrator这个管理员帐号没有设密码,这时就可以利用这个帐号进入电脑,方法是,按F8进入安全模式,即出现blos表后,就按F8.进去后可以给administrator设个密码了!!! 二.引用: 用 ...
  • 1.(a) 开机出现grub boot loader 开机选项菜单时,立即点击键盘任意鍵,boot loader 会暂停. (b) 按下’e’,编辑选项菜单(c) 移动上下鍵至linux16 核心命令行 linux16 /vmlinuz-3.10.0-123.el7.x86_64 root=UUID
  • 


    		    DZ X1.5论坛將&quot;登錄&quot;、&quot;註冊&quot;和&quot;找回密碼&quot;文字為按鈕樣式
    大家是否想把"登錄"."註冊"和"找回密碼"文字替換為按鈕樣式?? 沒問題,你只需修改兩個文件就能完全實現效果.此方法只适合DZ论坛X1.5版本 截圖演示: 美化前 美化后 美化方法: 1.打開正在使用的風格的common.css文件或ex ...
  • 


    		    Spads 工作組爲 Cikers 專案編寫的密碼庫使用說明
    Cikers密码库使用说明 History 1.1.0, 2014-11-28 Friday Shane Loo Li 初版 1.1.1, 2014-11-30 Sunday Shane Loo Li 增加了Mac版的国内下载地址,增加了编辑备注的意义,增加了对backup组的操作建议 1 使用密码 ...
  • 1. What is SSH? SSH 为 Secure Shell 的缩写,SSH 为建立在应用层和传输层基础上的安全协议.SSH 是目前较可靠,专为远程登录会话和其他网络服务提供安全性的协议.利用 SSH 协议可
一周排行
  • 


    		    關于android USB Host編程的一些總結
    以前没有接触过android USB Host编程.来到这个公司后,一边做着测试项目,一边
  • 玩轉單元測試之WireMock  Web服務模擬器
    玩转单元测试之WireMock -- Web服务模拟器   WireMock 是一个灵活的 ...
  • 


    		    〖ExtJS〗之Panel實例
    面板Panel是ExtJS控件的基础,很高级控件都是在面板的基础上扩展的,还有其它大多数控
  • 什么是TSD   为了Angular2做了一些技术准备. 首先遇到的是TSD,其实我们哪怕不需要它也没有关系,但……TypeScript毕竟还是比较新,我们很难知道目前现流行的一些库是否已经开始支持TypeScrip
  • 在win下配置ionic可以参考七月的这篇博客:http://www.cnblogs.com/shikelong/p/4480975.html. 依照七月的思路基本可以创建一个ionic项目了,下面我主要介绍一下怎样
  • bzoj1029 JSOI2007建築搶修
    1029: [JSOI2007]建筑抢修 Time Limit: 4 Sec  Memor
  • mono是.NET在Linux下的的开源实现, 主要的运行方式分为两种 apache + mod_mono nginx + fastcgi (mono) 考虑到nginx性能更好,这里讲述第二种实现方法 因为Ubun
  • 没有经过处理kb888111是拒绝安装在DC sp2上的 下载kb888111 解压找出for 2003版本的 进去commonfiles目录,把HDAUDBUS.INF HDAUDIO.INF拷贝到windows/ ...
  • SDK Manager   下载demo后,可以到SDK目录下面找 例如 C:\Program Files (x86)\Java\adt-bundle-windows-x86\sdk\samples\android-
  • HV4KJ-2X10K-VZ768-DRAGP-8CU2FMY63N-D0HEZXC1-HV37JL