注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2894]世界线  

2015-05-14 15:23:42|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2894: 世界线

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 42  Solved: 11
[Submit][Status][Discuss]

Description

由于春希对于第二世代操作的不熟练,所以刚使用完invasion process便掉落到了世界线之外,错综复杂的平行世界信息涌入到春希的意识中。春希明白了事件的真相。
在一个冬马与雪菜同时存在的世界里,傲娇的冬马最终还是博得了春希的内心。然而看着好友雪菜的消瘦,内心愧疚的冬马启动了第二世代操作,想找到一个雪菜最终成功的世界,却发现哪里都没有。绝望的冬马决定耗尽自己全部的第二世代操作点数,自创一个没有自己只有雪菜与春希的世界。
虽然这个世界一开始效果很好,春希与雪菜很快的被命运撮合在了一起,然而没有了冬马的雪菜,如没有了大海的沙滩,失去了傍依。
虽然世界里没有冬马的存在,但是由于冬马创造时的疏忽,这个世界里的雪菜依然存在着因独占春希而产生的对冬马的愧疚感,这种愧疚感折磨着雪菜,最终雪菜选择了自毁忘记春希。
看着这一切的春希深知不管是三个人一起的快乐,还是两个人独处的甜蜜,都无法消除冬马与雪菜内心的自责,无论如何修改世界,三人都只会更加痛苦,于是春希使用了自己剩余的全部操作点数,念出了key world:WhiteAlbum2,开始了initialization process.
在initialization process中,春希需要整理世界线,才能回归原本的世界。
世界线是一棵根节点为1的树,每个节点为1个字符。规定树上的子串为从某个节点(不一定是1号节点)出发往其子节点走所形成的字符串。每一个子串相当于一个平行世界,要想重构世界,就需要知道两个信息:
1.    不同子串的个数
2.    将不同的子串排序后,字典序第k-1小的子串。
如图所示为一个世界线的样例,从4->5的子串为bb,1->5的为abb 

Input

第一行两个整数n,q表示节点个数以及询问个数
第二行n个字符,表示编号为i的字符是什么。
接下来n-1行表示一棵树。
接下来q行,每行一个整数k

Output

第一行为不同支付串个数。
接下来q行为q个询问的答案(注意输出的是第k-1小的子串,如果K=1请直接换行),如果不存在(不包括k=1)输出-1.

Sample Input

8 1 abcbbaca 1 2 2 3 1 4 4 5 4 6 4 7 1 8 5

Sample Output

12 aba 【数据规模和约定】 12%:n<=10 另有48%为一条链; 100%: n<=250000,q<=50000.

Solution

就是BZOJ3998变成广义后缀自动机,剩下都一样。这题空串也算一种子串。

Code

/**************************************************************
    Problem: 2894
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:2160 ms
    Memory:57760 kb
****************************************************************/
 
#include<cstdio>
#include<cstring>
#define N 320010
int n,m,k,x,y,et,la[N],len[N],tot=1,S=1,root[N],ch[N][26],fail[N],vis[N],fa[N],i,c[N],maxl,id[N];long long cnt[N];
char s[N],*O;
struct E{int to,nxt;}e[500010];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
int add(int p,char c){
    if(ch[p][c]&&len[p]+1==len[ch[p][c]])return ch[p][c];
    int np=++tot;
    for(len[np]=len[p]+1;p&&!ch[p][c];p=fail[p])ch[p][c]=np;
    if(!p)fail[np]=S;
    else if(len[p]+1==len[ch[p][c]])fail[np]=ch[p][c];
    else{
        int q=ch[p][c],r=++tot;
        fail[r]=fail[q],fail[q]=fail[np]=r;len[r]=len[p]+1;
        memcpy(ch[r],ch[q],sizeof(ch[q]));
        for(;p&&ch[p][c]==q;p=fail[p])ch[p][c]=r;
    }
    return np;
}
void dfs(int x){
    root[x]=add(root[fa[x]],s[x]-'a');
    for(vis[x]=1;la[x];la[x]=e[la[x]].nxt)
#define to e[la[x]].to
    if(!vis[to])fa[to]=x,dfs(to);
#undef to
}
int main(){
    scanf("%d%d",&n,&m);scanf("%s",s+1);root[0]=1;
    for(i=1;i<n;i++)scanf("%d%d",&x,&y),adde(x,y),adde(y,x);
    for(dfs(1),i=1;i<=tot;i++)cnt[i]=1,c[len[i]]++,len[i]>maxl?maxl=len[i]:1;
    for(i=1;i<=maxl;i++)c[i]+=c[i-1];
    for(i=tot;i;i--)id[c[len[i]]--]=i;
    for(i=tot;i;i--)
    for(x=id[i],y=0;y<26;y++)cnt[x]+=cnt[ch[x][y]];
    for(printf("%lld\n",cnt[1]);m--;*O++=0,puts(s)){
        scanf("%d",&k);O=s;
        if(k>cnt[1])*O++='-',*O++='1';
        else if(k){
            for(x=S;k>1;){
                for(k--,y=0;y<26;y++)
                if(cnt[ch[x][y]]<k)k-=cnt[ch[x][y]];
                else{*O++=y+'a',x=ch[x][y];break;}
            }
        }
    }
}

  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018