2434: [Noi2011]阿狸的打字机 - #include <Seter> - using namespace Orz;
2434: [Noi2011]阿狸的打字机
http://www.zybbs.org/JudgeOnline/problem.php?id=2434
| RunID | User | Problem | Result | Memory | Time | Language | Code Length | Submit Time |
| 198975 | Seter | 2434 | Accepted | 20760 kb | 352 ms | C/Edit | 1562 B | 2012-02-03 14:26:54 |
做了4小时……最后发现问题在于我的AC自动机模板是错的……一直没怀疑……555这么弱怎么活……
不过最后1Y+Rank1，代码长度也是最短的（DYH大神1.9KB+），还是比较满意的结果！
这题同时考察了AC自动机和维护DFS序两个点，如果你对AC自动机理解得好的话一下子就能看出怎么做。同时ymNOI虐场的CLJ大神……
首先粗略地介绍一下AC自动机，这是一个在字母表较小的情况下线性的多串匹配算法。把所有目标串构成一个trie树，对于每个节点，记录一个fail指针表示如果匹配失败，则最近能跳到哪里。比如x的fail指向y，则说明root..x这个字符串的后缀是根..y，且对于所有root..x的后缀，root..y是最长的一个在trie中的。
构出trie后，点x的fail指针可以通过它父亲f的fail指针算出来。假设x对应字符c，依次检查f->fail,f->fail->fail,f->fail->fail->fail……root，如果有一个存在字符为c的儿子t，则x->fail=t，否则x->fail=root，这个还是很好想的……
问题在于处理顺序，我就是这里2X了。正确方法应该是弄个队列，一开始只有root，每次处理完一个点后把这个点所有儿子加进来即可。至于为什么……呃……不知道 T^T
对于这题，先构出AC自动机。然后对于一个询问(x,y)，暴力的做法是，枚举root..y上的每一个点作为终点（即这个点为最后一个字符），不断取fail指针，如果能跳到x，则说明这个位置匹配成功，这个应该很好理解。
考虑能跳到x的节点，如果将fail指针反过来，这就是一棵树，叫做fail tree。在fail tree中，能跳到x的节点就是x的子树节点！只要找出这些节点中root..y中的节点有几个就可以了。
离线查询子树信息可以用DFS序来做，一个点的子树在DFS序中是一段，可以用BIT等维护，不说了。遍历整个trie，当询问到节点y时，对于每个询问(x,y)，我们需要知道在fail tree中，x的子树节点中有几个是在root..y中的。即在遍历到y时，BIT中保存的是root..y这些节点的信息，这些点每个点的值是1，其它点是0。那么只要遍历一个点的儿子之前将其设为1，遍历完改回0就可以了，询问即是询问一段的和。
如果不懂的话先自己想想……也可以在下面留言恩。这个还是比较麻烦的，我想了好久，最重要的是要注意，这里有trie和fail tree两个树，其中trie是用来遍历和构造fail指针的，fail tree只需要记录它的DFS序，然后更新都是在DFS序上做手脚。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <stdio.h>#define maxn 100010#define T struct trie#define E struct edge#define Q struct qzT{T*f,*fail,*c[26];int id}t,stt[maxn],*que[maxn]={&t};E{E*next;int y}*map[maxn],st[maxn];Q{Q*next;int x,ans}*q[maxn],stq[maxn];int id[maxn],s[maxn][2],n,a[maxn],bq=-1,eq=1;char str[2000000],*p=str;inline void I(x,y){for(;x<=n;x+=x&-x)a[x]+=y;}inline S(x){int t=0;for(;x;x-=x&-x)t+=a[x];return t;}inline getint(){ int re=0; while(*p<'0'||*p>'9')p++; while(*p>='0'&&*p<='9')re=re*10+*p++-48; return re;}void Init(x){E*p=map[x];for(s[x][0]=++n;p;p=p->next)Init(p->y);s[x][1]=n;}void Travel(T*x){ Q*p=q[x->id];int i=-1; for(;p;p=p->next)p->ans=S(s[p->x][1])-S(s[p->x][0]-1); while(++i!=26)if(x->c[i]){ I(s[x->c[i]->id][0],1); Travel(x->c[i]); I(s[x->c[i]->id][0],-1); }}main(){ int m=1,i=0,y;T*f=&t;fread(p,1,2000000,stdin);p--; while(*++p>0)if(*p=='P')id[i++]=f->id; else if(*p=='B')f=f->f; else if(*p<'a'||*p>'z')break; else if(f->c[y=*p-'a'])f=f->c[y]; else(f->c[y]=stt+m)->f=f,(f=f->c[y])->id=m++; while(++bq!=eq)for(i=-1;++i!=26;)if(que[bq]->c[i]){ for(f=que[bq]->fail;f&&!f->c[i];)f=f->fail; f=(que[eq]=que[bq]->c[i])->fail=f?f->c[i]:&t; st[eq].y=que[eq]->id;st[eq].next=map[f->id];map[f->id]=st+eq++; }for(Init(0),i=m=getint();i--;q[y]=stq+i){ stq[i].x=id[getint()-1]; stq[i].next=q[y=id[getint()-1]]; }for(Travel(&t);m--;)printf("%d\n",stq[m].ans); return 0;} |
By Seter
评论 (0)