BZOJ2746: [HEOI2012]旅行问题(AC自动机 LCA)
2018-07-03 01:00:54来源:博客园 阅读 ()
Submit: 1188 Solved: 383
[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
aabb babb
2
1 3 2 3
1 4 2 4
Sample Output
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。
Source
想骂人,。。。。
这题我一开始按fail图做的,然后死活90分,调了一下午,心态爆炸。。
说出来泥萌可能不信,如果我要是在2012年以前出生,这题可能就是我出的了qwq。。
刚学完AC自动机的时候我就感觉能在AC自动机的fail树上搞事情,比如求个lca啊,询问个路径和啊,断开一条边啊之类的。
然后我自己证了一个多小时,得到一条性质:
点$x$与点$y$在$fail$树中$lca$处的到的字符串,为模式串中与$x,y$公共后缀最长的前缀
本来想把这题出出来着,结果百度了一下:fail树+lca,正好找到这题,mmp,,
// luogu-judger-enable-o2 // luogu-judger-enable-o2 #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> #include<map> using namespace std; const int MAXN = 1 << 20, mod = 1000000007; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int N; char s[MAXN]; int ch[MAXN][26], root = 0, tot = 0; int bg[MAXN], pos[MAXN << 1], cnt = 0, fa[MAXN][21], deep[MAXN];; long long val[MAXN]; void insert(char *s, int ID) { bg[ID] = cnt; int N = strlen(s + 1); int now = root; for(int i = 1; i <= N; i++) { int x = s[i] - 'a'; if(!ch[now][x]) ch[now][x] = ++tot; val[ch[now][x]] = ((val[now] * 26) % mod + x % mod) % mod; now = ch[now][x]; pos[++cnt] = now; } } vector<int> v[MAXN]; void GetFail() { queue<int> q; deep[root] = 1; //for(int i = 0; i <= tot; i++) fail[i] = 1; fa[root][0] = 1; for(int i = 0; i < 26; i++) if(ch[root][i]) q.push(ch[root][i]), fa[ch[root][i]][0] = 1; while(!q.empty()) { int p = q.front(); q.pop(); if(p != 1) deep[p] = deep[fa[p][0]] + 1; for(int i = 0; i < 26; i++) { if(ch[p][i]) { int t = p; for(t = fa[p][0]; t != 1 && !ch[t][i]; t = fa[t][0]); if(ch[t][i]) fa[ch[p][i]][0] = ch[t][i]; else fa[ch[p][i]][0] = 1; //fa[ch[p][i]][0] = ch[fa[p][0]][i], q.push(ch[p][i]); } } } } void Pre() { for(int i = 1; i < 21; i++) for(int j = 0; j <= tot; j++) fa[j][i] = fa[fa[j][i - 1]][i - 1]; } int LCA(int x, int y) { if(deep[x] < deep[y]) swap(x, y); for(int i = 20; i >= 0; i--) if(deep[fa[x][i]] >= deep[y]) x = fa[x][i]; if(x == y) return x; for(int i = 20; i >= 0; i--) if(fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i]; return fa[x][0]; } main() { #ifdef WIN32 freopen("a.in", "r", stdin); // freopen("a.out", "w", stdout); #endif N = read(); for(int i = 1; i <= N; i++) scanf("%s", s + 1), insert(s, i); GetFail(); Pre(); int Q = read(); while(Q--) { int S1 = read(), L1 = read(), S2 = read(), L2 = read(); int ans = LCA(pos[bg[S1] + L1], pos[bg[S2] + L2]); printf("%lld\n", val[ans]); } }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- 算法训练 旅行家的预算 2020-02-23
- 洛谷P1523 旅行商简化版(DP) 2019-10-17
- BZOJ1050: [HAOI2006]旅行comf(并查集 最小生成树) 2018-07-13
- 1405 奶牛的旅行 2018-06-17
- bzoj 1143: [CTSC2008]祭祀river / 2718: [Violet 4]毕业旅 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash