首页 > 代码库 > BZOJ3926 ZJOI2015 诸神眷顾的幻想乡 后缀自动机+DFS
BZOJ3926 ZJOI2015 诸神眷顾的幻想乡 后缀自动机+DFS
题意：给定一颗字符树，求树中路径所构成的不同的字符串的数量，其中AB和BA视作不同的字符串
题解：
题目里有这样一句话：太阳花田的结构比较特殊，只与一个空地相邻的空地数量不超过20个。
一共有10W个点，却只有20个叶子……因此树上所有的字串就是以叶子为起点搜索出的所有字串，丽洁姐真的好善良啊- -（无雾）
这样从每个点开始就能跑出来一颗Trie树，对Trie构造广义后缀自动机——每个节点看成是一个根，在后面加字符的时候和普通的SAM一样。
然后在SAM上用DFS统计不同字串的数量即可
#include <queue>#include <cstdio>#include <cstring>#include <cstdlib>#include <climits>#include <iostream>#include <algorithm>using namespace std;#define ll long longconst int MAXC=10+2;const int MAXN=100000+2;struct HASH{ int u; HASH *next; HASH(){} HASH(int _u,HASH *_next):u(_u),next(_next){}}*table[MAXN],mem[2*MAXN];struct SAM{ int v; SAM *child[MAXC],*f; bool flag; SAM(){} SAM(int _v):v(_v),f(0),flag(0){ memset(child,0,sizeof(child));}}*root,*last=root=new SAM(0),*node[MAXN];int N,C,c[MAXN],d[MAXN],cnt;queue<SAM *> q;void Insert(int u,int v){ table[u]=&(mem[cnt++]=HASH(v,table[u]));}SAM *Extend(SAM *&x,int c){ if(x->child[c] && x->child[c]->v==x->v+1) return x->child[c]; SAM *p=x,*np=new SAM(p->v+1); while(p && !p->child[c]) p->child[c]=np,p=p->f; if(!p) np->f=root; else{ SAM *q=p->child[c]; if(q->v==p->v+1) np->f=q; else{ SAM *nq=new SAM(p->v+1); memcpy(nq->child,q->child,sizeof(q->child)); nq->f=q->f,q->f=np->f=nq; while(p && p->child[c]==q) p->child[c]=nq,p=p->f; } } return np;}void DFS(int x,int f){ node[x]=Extend(node[f],c[x]); for(HASH *p=table[x];p;p=p->next) if(p->u!=f) DFS(p->u,x);}ll BFS(SAM *x){ ll ret=0; q.push(x); SAM *t; while(!q.empty()){ t=q.front(),q.pop(); if(t!=x) ret+=t->v-t->f->v; for(int i=0;i<C;i++) if(t->child[i] && !t->child[i]->flag) t->child[i]->flag=1,q.push(t->child[i]); } return ret;}int main(){ scanf("%d %d",&N,&C); for(int i=1;i<=N;i++) scanf("%d",c+i); for(int i=1,a,b;i<N;i++){ scanf("%d %d",&a,&b); d[a]++,d[b]++; Insert(a,b),Insert(b,a); } node[0]=root; for(int i=1;i<=N;i++) if(d[i]==1) DFS(i,0); printf("%lld\n",BFS(root)); return 0;}
BZOJ3926 ZJOI2015 诸神眷顾的幻想乡 后缀自动机+DFS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。