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

n+e

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

 
 
 

日志

 
 

[BZOJ2746][HEOI2012]旅行问题  

2015-04-23 21:38:53|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2746: [HEOI2012]旅行问题

Time Limit: 30 Sec  Memory Limit: 256 MB
Submit: 531  Solved: 188
[Submit][Status][Discuss]

Description

yz是Z国的领导人,他规定每个地区的名字只能为26个小写拉丁字母的一个。由于地 区数有可能超过26个,便产生了一个问题,如何辨别名字相同的地区?于是yz规定,一个 地区的描述必须包含它的所有上级,且上级按次序排列。于是,一个地区的描述是一个字符 串。比如说,一个地区的名字为c,它的上级为b,b的上级为a,a没有上级,那么这个地 区就描述为abc。显然,这个描述同时包含了c的上级b和b的上级a的描述,分别为ab和a。 值得注意的是,每个地区最多有一个上级,同一上级的地区之间名字不同,没有上级的 地区之间名字不同。现在,yz对外公布了n个地区的描述,这些描述中包含了Z国所有地区的描述,并让 你处理来访者的旅行问题。现有m对人访问这个国家,对于每对人,第一个人喜欢第i个描述中的第j个地区,设 这个地区描述为s1,第二个人喜欢第k个描述中的第l个地区,设这个地区描述为s2。他们为了统一行程,决定访问描述为s的地区(显然他们只关心地区的名字,并非是地区本身), 设s的长度为t,s需要满足以下条件: 
1:t<=j, t<=l; 
1:s[1..t] = s1[j-t+1 … j], s[1..t] = s2[l-t+1 … l];(即s为s1中1到k位 与s2中1到l位的公共后缀) 
2:t最大化。 
为了不使输出过大,你只需把这个字符串按照如下生成的26进制数转成10进制后mod 1000000007后输出: 
a->0 
b->1 



z->25 
比如地区cab被编码成2 *    26? + 0 * 26? + 1 * 26? = 1353。 

Input

第一行给定一个整数n 
第2…n+1行:每i+1行给定一个字符串a[i],表示第i个描述。 
接下来一行一个整数m 
接下来m行:每行给定四个整数i,j,k,l,字母含义与题目描述一致。 

Output

共m行,每行一个整数,表示答案字符串的编码。 

Sample Input

2 aabb babb 2 1 3 2 3 1 4 2 4

Sample Output

1 1 【样例说明】 询问1中的公共后缀有ab和b,但是没有ab这个地区,只有b地区,所以只能选择b这个 地区; 询问2中的公共后缀有abb、bb和b,但是没有abb和bb这两个地区,只有b地区,所以 只能选择b这个地区。

HINT

【数据范围】

设这个国家地区总数数为tot(注意:输入的字符串总长度可能超过tot!) 对于30%的数据,满足tot,m,n<=100; 

对于50%的数据,满足tot,m,n<=1000; 

对于80%的数据,满足tot,m,n<=100000; 

对于100%的数据,满足tot,m,n<=1000000; 

保证输入文件不超过20MB。 

Solution

被题意坑了好久。。。
题意是询问某两个串a,b的前缀,求最大的L使得a,b有相等的长为L的后缀并且还等于a,b串的某串前缀。
做法很巧妙,对所有串跑一遍AC自动机,拎出fail树,询问就是两点间的LCA。
fail树的性质很巧妙的应用在了这题里面,感觉好神奇

Code

/**************************************************************
    Problem: 2746
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:4476 ms
    Memory:235300 kb
****************************************************************/
 
#include<cstdio>
#define N 1<<20
#define mod 1000000007
int n,m,i,j,tot,ch[N][26],las,fail[N],et,la[N],fa[N][18],dep[N],q[N<<1],l=1,r,pos[N<<1],len[N],op[N],a,b,c,d;char s[N];
struct E{int to,nxt;}e[N<<1];
#define adde(x,y) (e[++et]=(E){y,la[x]},la[x]=et)
void add(char c){
    if(!ch[las][c])ch[las][c]=++tot,op[tot]=(26LL*op[las]+c)%mod;
    las=ch[las][c];
}
int query(int x,int y){
    int k,i=0;
    if(dep[x]<dep[y])k=x,x=y,y=k;
    for(k=dep[x]-dep[y];k;k>>=1,i++)
    if(k&1)x=fa[x][i];
    if(x==y)return x;
    for(i=17;~i;i--)if(fa[x][i]!=fa[y][i])
    x=fa[x][i],y=fa[y][i];
    return fa[x][0];
}
int aa;char cc;int F(){
    while(cc=getchar(),cc<'0'||cc>'9')if(cc==0)return aa;aa=cc-'0';
    while(cc=getchar(),cc>='0'&&cc<='9')aa=aa*10+cc-'0';return aa;
}
int main(){
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%s",s);las=0;len[i]=len[i-1];
        for(j=0;s[j];j++)add(s[j]-'a'),pos[++len[i]]=las;
    }
    for(i=0;i<26;i++)if(ch[0][i])q[++r]=ch[0][i],adde(0,ch[0][i]);
    for(;l<=r;l++)
    for(i=0;i<26;i++)
    if(ch[q[l]][i]){
        for(j=fail[q[l]];j&&!ch[j][i];j=fail[j]);
        fail[q[++r]=ch[q[l]][i]]=ch[j][i];
        adde(ch[j][i],q[r]);
    }
    for(dep[0]=1,q[l=r=0]=0;l<=r;l++)
    for(i=la[q[l]];i;i=e[i].nxt)
    if(!dep[e[i].to]){
        dep[q[++r]=e[i].to]=dep[q[l]]+1;
        fa[e[i].to][0]=q[l];
        for(j=0;fa[e[i].to][j];j++)fa[e[i].to][j+1]=fa[fa[e[i].to][j]][j];
    }
    for(scanf("%d",&m);m--;printf("%d\n",op[query(a,b)]))a=pos[len[F()-1]+F()],b=pos[len[F()-1]+F()];
}

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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