「kuangbin带你飞」专题十七 AC自动机
layout: post 传送门 A.HDU2222 Keywords Search模板题。给出N个单词,后给你一个长串,问长串中有几个单词。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f; const int maxm=500010; struct Trie{ int next[maxm][26],fail[maxm],end[maxm]; int root,L; int newnode(){ for(int i=0;i<26;i++) next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } end[now]++; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); for(int i=0;i<26;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int query(char buf[]){ int len=strlen(buf); int now=root; int res=0; for(int i=0;i<len;i++){ now=next[now][buf[i]-'a']; int temp=now; while(temp!=root){ res+=end[temp]; end[temp]=0; temp=fail[temp]; } } return res; } void debug(){ for(int i=0;i<L;i++){ printf("id =%3d,fail = %3d,end = %3d,chi = [",i,fail[i],end[i]); for(int j=0;j<26;j++) printf("%2d",next[i][j]); printf("]n"); } } }; char buf[maxn]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); cin>>buf; cout<<ac.query(buf)<<endl; } return 0; } B.HDU2896 病毒侵袭和A题一样的模板题,不过要求我们计算长串中出现了那些字符串,在ac自动机的end数组改成是哪一个字符串的编号然后在查询的时候用used数组记录一下既可。 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e6+50; const ll inf=0x3f3f3f3f3f3f; const int maxm=500010; struct Trie{ int next[maxm][128],end[maxm]; bool used[550]; int root,L; int newnode(){ for(int i=0;i<128;i++) next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[],int id){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]]==-1) next[now][buf[i]]=newnode(); now=next[now][buf[i]]; } end[now]=id; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<128;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); for(int i=0;i<128;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } bool query(char buf[],int n,int id){ int len=strlen(buf); int now=root; int res=0; for(int i=0;i<=n;i++)used[i]=false; bool flag=false; for(int i=0;i<len;i++){ now=next[now][buf[i]]; int temp=now; while(temp!=root){ if(end[temp]){ used[end[temp]]=true; flag=true; } temp=fail[temp]; } } if(!flag)return false; else{ cout<<"web "<<id<<":"; for(int i=1;i<=n;i++) if(used[i])cout<<" "<<i; cout<<endl; return true; } } void debug(){ for(int i=0;i<L;i++){ printf("id =%3d,next[i][j]); printf("]n"); } } }; char buf[maxn]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int t; int n; cin>>n; ac.init(); for(int i=1;i<=n;i++){ cin>>buf; ac.insert(buf,i); } int m; ac.build(); cin>>m; int sum=0; for(int i=1;i<=m;i++){ cin>>buf; if(ac.query(buf,n,i))sum++; } cout<<"total: "<<sum<<endl; return 0; } C.HDU3065 病毒侵袭持续中
注意:这题是多组数据,但是题面上没写很坑~!
这题和B题一样的题意只不过题面很坑 #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=1e8+50; const ll inf=0x3f3f3f3f3f3f; const int maxm=500010; char word[1100][55]; struct Trie{ int next[maxm][128],end[maxm]; int used[1100]; int root,int n){ int len=strlen(buf); int now=root; int res=0; for(int i=0;i<=n;i++)used[i]=0; for(int i=0;i<len;i++){ now=next[now][buf[i]]; int temp=now; while(temp!=root){ if(end[temp]){ used[end[temp]]++; } temp=fail[temp]; } } for(int i=1;i<=n;i++){ if(used[i]){ cout<<word[i]<<": "<<used[i]<<endl; } } } void debug(){ for(int i=0;i<L;i++){ printf("id =%3d,end[i]); for(int j=0;j<128;j++) printf("%2d",next[i][j]); printf("]n"); } } }; char buf[maxn]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int t; int n; while(cin>>n){ ac.init(); for(int i=1;i<=n;i++){ cin>>word[i]; ac.insert(word[i],i); } int m; ac.build(); // ac.debug(); cin>>buf; ac.query(buf,n); } return 0; } D.ZOJ3430 Detect the Virus题意给你N个病毒(大小不超过64bytes子串)然后给你M个长串(大小不超过2048byte)问你长串没处理中有几个没处理的子串; 注意: 解法这题的难点在于把字符串根据题目要求模拟成变化前的样子,然后就是AC自动机板子题; #include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=998244353; const int maxn=2048*10; const ll inf=0x3f3f3f3f3f3f; const int maxm=512*64; struct Trie{ int next[maxm][260],L; int newnode(){ for(int i=0;i<260;i++) next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(int buf[],int id,int len){ //int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]]==-1) next[now][buf[i]]=newnode(); now=next[now][buf[i]]; } end[now]=id; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<260;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); for(int i=0;i<260;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void query(int buf[],int len){ //int len=strlen(buf); int now=root; int res=0; for(int i=0;i<=n;i++)used[i]=0; for(int i=0;i<len;i++){ now=next[now][buf[i]]; int temp=now; while(temp!=root){ if(end[temp]){ used[end[temp]]++; } temp=fail[temp]; } } int sum=0; for(int i=1;i<=n;i++){ if(used[i]){ sum++; } } cout<<sum<<endl; } void debug(){ for(int i=0;i<L;i++){ printf("id =%3d,end[i]); for(int j=0;j<260;j++) printf("%2d",next[i][j]); printf("]n"); } } }; int fun(char ch){ if(ch>='A'&&ch<='Z')return ch-'A'; if(ch>='a'&&ch<='z')return ch-'a'+26; if(ch>='0'&&ch<='9')return ch-'0'+52; if(ch=='+')return 62; if(ch=='/')return 63; } char buf[maxn]; int aa[maxn]; int after[maxn]; int gao(int n){ int t=0; ///00011010->01101000 for(int i=0;i<n;i+=4){ ///00000110->00000000 按照题意合并成八位的01101000 aa[t++]=((after[i]<<2)|(after[i+1]>>4));///取前一个的后六位 和后一个数的前两位 组成一个新的八位字符 ///因为前面i把i+1的前两个取走了,所有i+1现在只有六个中的后四个和i+2的前四个匹配; if(i+2<n)aa[t++]=((after[i+1]<<4&0xff)|(after[i+2]>>2)); ///因为前面i+1把i+2的前四个取走了,所有i+2现在只有六个中的两个和i+2的前六个匹配; if(i+3<n)aa[t++]=((after[i+2]<<6&0xff)|(after[i+3])); } return t; } Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; int n; while(cin>>n){ ac.init(); //cout<<"haha"<<endl; for(int i=1;i<=n;i++){ cin>>buf; // cout<<"here:?"<<endl; int len=strlen(buf); while(buf[len-1]=='=')len--; for(int j=0;j<len;j++)after[j]=fun(buf[j]); int k=gao(len); ac.insert(aa,k); } int m; ac.build(); cin>>m; while(m--){ cin>>buf; int len=strlen(buf); while(buf[len-1]=='=')len--; for(int j=0;j<len;j++)after[j]=fun(buf[j]); int k=gao(len); ac.query(aa,k); } cout<<endl; } return 0; } E.POJ2778 DNA Sequence题意给你N个病毒,问你有长度为L的DNA中有多少种是没有病毒的 思路所有病毒串构造一个AC自动机,这个AC自动机可以看作一张有向图,图上的每个顶点就是Trie树上的结点,每个结点都可以看作是某个病毒串的前缀,Trie树的根则是空字符串。 对于agc、c而言,如果我zou过 a-g-c-d 这个路径。 root / a c / g / c / d 由上面这个图可知 左边的d 和 右边的c都是危险节点。 但漏掉了左边上的c 所以如果fail指针指向那个节点是危险节点的话,那么当前节点也是危险节点 #include<algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <bitset> #include <queue> #include <map> #include <set> using namespace std; typedef long long ll; const ll mod=100000; const int maxn=10*10+5; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct Matrix{ unsigned long long mat[maxn][maxn]; int n; Matrix(){} Matrix(int _n){ n=_n; for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0; } Matrix operator *(const Matrix &b)const{ Matrix ret=Matrix(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ ret.mat[i][j]+=(mat[i][k]*b.mat[k][j])%mod; ret.mat[i][j]%=mod; } } } return ret; } unsigned long long pow_m(unsigned long long a,int n){ unsigned long long ret=1,tmp=a; while(n){ if(n&1)ret*=tmp; tmp*=tmp; n>>=1; }return ret; } Matrix pow_M(Matrix a,ll n){ Matrix ret=Matrix(a.n); for(int i=0;i<a.n;i++)ret.mat[i][i]=1; Matrix tmp=a; while(n){ if(n&1)ret=ret*tmp; tmp=tmp*tmp; n>>=1; } return ret; } }; struct Trie{ int next[maxn][4],fail[maxn],id['Z'+1]; bool end[maxn]; int root,L; int newnode(){ for(int i=0;i<4;++i)next[L][i]=-1; end[L++]=false; return L-1; } void init(){ L=0; id['A']=0;id['T']=1;id['C']=2;id['G']=3; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][id[buf[i]]]==-1)next[now][id[buf[i]]]=newnode(); now=next[now][id[buf[i]]]; } end[now]=true; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<4;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]])end[now]=true; for(int i=0;i<4;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } Matrix getMatrix(){ Matrix ret=Matrix(L); for(int i=0;i<L;i++){ for(int j=0;j<4;j++){ if(end[next[i][j]]==false&&end[i]==false) ret.mat[i][next[i][j]]++; } } return ret; } }; Trie ac; char buf[15]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; ll L; cin>>n>>L; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); Matrix mat=ac.getMatrix(); mat=mat.pow_M(mat,L); ll ans=0; for(int i=0;i<mat.n;i++){ ans=(ans+mat.mat[0][i])%mod; } cout<<ans<<endl; return 0; } F.HDU2243 考研路茫茫――单词情结题意跟上题一样,不过这题是让你求包括的个数,而且不仅仅是长度为L而且长度小于L的也要包括进去;可以通过上题很快求出不包括的,然后求和,在求出全部的26^1+...26^L的个数减去不包括的就是答案; 思路通过矩阵求出全部长度的可能和AC自动机求出来的矩阵的和,然后相减 #include<algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <bitset> #include <queue> #include <map> #include <set> using namespace std; typedef long long ll; typedef unsigned long long ull; const ll mod=2147483648LL; const ll maxn=5*6+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; struct Matrix{ unsigned long long mat[maxn][maxn]; int n; Matrix(){} Matrix(int _n){ n=_n; for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0; } Matrix operator *(const Matrix &b)const{ Matrix ret=Matrix(n); for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ ret.mat[i][j]+=(mat[i][k]*b.mat[k][j]); } } } return ret; } unsigned long long pow_m(unsigned long long a,ll n){ Matrix ret=Matrix(a.n); for(int i=0;i<a.n;i++)ret.mat[i][i]=1; Matrix tmp=a; while(n){ if(n&1)ret=ret*tmp; tmp=tmp*tmp; n>>=1; } return ret; } }; struct Trie{ int next[maxn][26],fail[maxn]; bool end[maxn]; int root,L; int newnode(){ for(int i=0;i<26;++i)next[L][i]=-1; end[L++]=false; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1)next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } end[now]=true; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]])end[now]=true; for(int i=0;i<26;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } Matrix getMatrix(){ Matrix ret=Matrix(L+1); for(int i=0;i<L;i++){ for(int j=0;j<26;j++){ if(end[next[i][j]]==false) ret.mat[i][next[i][j]]++; } } for(int i=0;i<L+1;i++)ret.mat[i][L]=1; return ret; } }; Trie ac; char buf[15]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; ll L; while(cin>>n>>L){ ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); Matrix mat=ac.getMatrix(); mat=mat.pow_M(mat,L); ull res=0; for(int i=0;i<mat.n;i++)res+=mat.mat[0][i]; res--; ull ans=0; Matrix all=Matrix(2);all.mat[0][0]=26;all.mat[0][1]=all.mat[1][1]=1; /* 26 1 × Sn -> Sn+1 0 1 × 26 -> 26 */ all=all.pow_M(all,L); ans=all.mat[0][1]*26; cout<<ans-res<<endl; } return 0; } G.POJ - 1625 Censored!题意n,m,p;n代表总共有n个字母,m代表字符串的长度为m,p代表病毒字符串的个数;题目让你求的是不包含病毒的字符串长度为m的个数为多少。 题解较麻烦的题,但是不要被代码长度吓到了 不过没有取模操作,需要大数。 大数不可以矩阵快速幂吗?内存不够…… 使用dp递推,递推公式也比较简单。 #include<algorithm> #include <iostream> #include <stdlib.h> #include <string.h> #include <stdio.h> #include <math.h> #include <time.h> #include <vector> #include <bitset> #include <queue> #include <map> #include <set> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=1e5+50; const ll inf=0x3f3f3f3f3f3f3f3fLL; ll gcd(ll a,ll b){while(b){ll t=a%b;a=b;b=t;}return a;} ll lcm(ll a,ll b){return a*b/__gcd(a,b);} map<char,int>mp; int N,M,P; struct Matrix{ int mat[110][110]; int n; Matrix(){} Matrix(int _n){ n=_n; for(int i=0;i<n;i++)for(int j=0;j<n;j++)mat[i][j]=0; } }; struct Trie{ int next[110][256],fail[110];bool end[110]; int L,root; int newnode(){ for(int i=0;i<256;i++){ next[L][i]=-1; } end[L++]=false; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][mp[buf[i]]]==-1) next[now][mp[buf[i]]]=newnode(); now=next[now][mp[buf[i]]]; } end[now]=true; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<256;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]]==true)end[now]=true; for(int i=0;i<256;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } Matrix getMatrix(){ Matrix res=Matrix(L); for(int i=0;i<L;i++) for(int j=0;j<N;j++) if(end[next[i][j]]==false)res.mat[i][next[i][j]]++; return res; } }; struct BigInt{ const static int mod=10000; const static int DLEN=4; int a[600],len; BigInt(){ memset(a,sizeof(a)); len=1; } BigInt(int v){ memset(a,sizeof(a)); len=0; do{ a[len++]=v%mod; v/=mod; }while(v); } BigInt(const char s[]){ memset(a,sizeof(a)); int L=strlen(s); len=L/DLEN; if(L%DLEN)len++; int index=0; for(int i=L-1;i>=0;i-=DLEN){ int t=0; int k=i-DLEN+1; if(k<0)k=0; for(int j=k;j<=i;j++) t=t*10+s[j]-'0'; a[index]=t; } } BigInt operator +(const BigInt &b)const{ BigInt res; res.len=max(len,b.len); for(int i=0;i<res.len;i++){ res.a[i]+=((i<len)?a[i]:0)+((i<b.len)?b.a[i]:0); res.a[i+1]+=res.a[i]/mod; res.a[i]%=mod; } if(res.a[res.len]>0)res.len++; return res; } BigInt operator *(const BigInt &b)const { BigInt res; for(int i = 0; i < len;i++) { int up = 0; for(int j = 0;j < b.len;j++) { int temp = a[i]*b.a[j] + res.a[i+j] + up; res.a[i+j] = temp%mod; up = temp/mod; } if(up != 0) res.a[i + b.len] = up; } res.len = len + b.len; while(res.a[res.len - 1] == 0 &&res.len > 1)res.len--; return res; } void output() { printf("%d",a[len-1]); for(int i = len-2;i >=0 ;i--) printf("%04d",a[i]); printf("n"); } }; char buf[1010]; BigInt dp[2][110]; Trie ac; int main() { while(scanf("%d%d%d",&N,&M,&P)==3){ gets(buf); gets(buf); mp.clear(); int len=strlen(buf); for(int i=0;i<len;i++)mp[buf[i]]=i; ac.init(); for(int i=0;i<P;i++){ gets(buf); ac.insert(buf); } ac.build(); Matrix a=ac.getMatrix(); int now=0; dp[now][0]=1; for(int i=1;i<a.n;i++)dp[now][i]=0; for(int i=0;i<M;i++){ now^=1; for(int j=0;j<a.n;j++)dp[now][j]=0; for(int j=0;j<a.n;j++){ for(int k=0;k<a.n;k++){ if(a.mat[j][k]>0){ dp[now][k]=dp[now][k]+dp[now^1][j]*a.mat[j][k]; } } } } BigInt ans=0; for(int i=0;i<a.n;i++)ans=ans+dp[now][i]; ans.output(); } return 0; } H.HDU - 2825 Wireless Password题意给你一堆(不超过10个)长度不超过10的单词,然后问你长度为N句子并且包含K个不同单词的个数有多少个; 题解先利用ac自动机求出各种状态,(总共不超过10*10)个,然后dp枚举长度,状态,和已有个数,已有个数可以用状态压缩O(1)求出来 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=20090717; const int maxn=(1<<10)+5; const ll inf=0x3f3f3f3f3f3f3f3fLL; int gcd(int a,int b){while(b){int t=a%b;a=b;b=t;}return a;} int lcm(int a,int b){return a*b/gcd(a,b);} int dp[110][110][maxn]; struct Trie{ int next[110][26],fail[110],end[110]; int root,L; int newnode(){ for(int i=0;i<26;i++) next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[],int id){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } end[now]|=(1<<id); } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); end[now]|=end[fail[now]]; for(int i=0;i<26;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int query(char buf[]){ int len=strlen(buf); int now=root; int res=0; for(int i=0;i<len;i++){ now=next[now][buf[i]-'a']; int temp=now; while(temp!=root){ res+=end[temp]; end[temp]=0; temp=fail[temp]; } } return res; } }; Trie ac; int num[maxn]; int slove(int n,int m,int k){ memset(dp,sizeof(dp)); dp[0][0][0]=1; for(int i=0;i<n;i++){//长度 for(int j=0;j<ac.L;j++){//状态 for(int l=0;l<(1<<m);l++){//个数 if(dp[i][j][l]){ for(int p=0;p<26;p++){ int nowj=ac.next[j][p]; int nowl=l|(ac.end[nowj]); dp[i+1][nowj][nowl]=(dp[i+1][nowj][nowl]+dp[i][j][l])%mod; } } } } } ll sum=0; for(int i=0;i<ac.L;i++){ for(int j=0;j<(1<<m);j++){ if(num[j]>=k){ sum=(sum+dp[n][i][j])%mod; } } } return sum; } int n,m,k; char buf[150]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); memset(num,sizeof(num)); for(int i=0;i<maxn;i++){ for(int j=0;j<=10;j++){ if(i&(1<<j))num[i]++; } } while(cin>>n>>m>>k){ if(n==0&&m==0&&k==0)break; ac.init(); for(int i=0;i<m;i++){ cin>>buf; ac.insert(buf,i); } ac.build(); cout<<slove(n,k)<<endl; } return 0; } I.HDU - 2296 Ring题意给定m个不同的单词,单词由小写字母组成,每个单词都有自身的价值。现在你要设计一个字符串,字符串的长度不能超过n。如果字符串里面包含了某个单词,就可以获得相应的价值,价值可以重复计算。单词可以相互重叠。 题解模板AC自动机,不过加了个字符串储存 不过不知道这是不是就是传说中的trie图 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=20090717; const int maxn=(1<<10)+5; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} int dp[55][1100]; string ss[55][1100]; int money[150]; int cmp(string a,string b){ if(a.length()==b.length())return a<b; else return a.length()<b.length(); } int mycmp(string a,string b){ if(a.length()==b.length())return a<b; else return a.length()<b.length(); } struct Trie{ int next[1100][26],fail[1010],end[1010]; int root,int money){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); now=next[now][buf[i]-'a']; } end[now]=money; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); end[now]+=end[fail[now]]; for(int i=0;i<26;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int query(char buf[]){ int len=strlen(buf); int now=root; int res=0; for(int i=0;i<len;i++){ now=next[now][buf[i]-'a']; int temp=now; while(temp!=root){ res+=end[temp]; end[temp]=0; temp=fail[temp]; } } return res; } string slove(int n,int m){ for(int i=0;i<=n;i++)for(int j=0;j<L;j++)ss[i][j]=""; dp[0][0]=0; int ma=0; for(int i=0;i<n;i++){ for(int j=0;j<L;j++){ if(dp[i][j]!=-inf){ for(int k=0;k<26;k++){ if(next[j][k]!=-1){ int nex=next[j][k]; string nowstr=ss[i][j]+char(k+'a'); int nowmoney=dp[i][j]+end[nex]; if(nowmoney>dp[i+1][nex]||(nowmoney==dp[i+1][nex]&&mycmp(nowstr,ss[i+1][nex]))){ dp[i+1][nex]=nowmoney; ss[i+1][nex]=nowstr; if(dp[i+1][nex]>ma){ ma=dp[i+1][nex]; } } } } } } } vector<string>ve; for(int i=0;i<=n;i++){ for(int j=0;j<L;j++){ if(dp[i][j]==ma){ ve.push_back(ss[i][j]); } } } sort(ve.begin(),ve.end(),cmp); return ve[0]; } }; Trie ac; int n,k; char buf[150][150]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; cin>>t; while(t--){ cin>>n>>m; ac.init(); for(int i=0;i<m;i++)cin>>buf[i]; for(int i=0;i<m;i++)cin>>money[i],ac.insert(buf[i],money[i]); memset(dp,-inf,sizeof(dp)); ac.build(); cout<<ac.slove(n,m)<<endl; } return 0; } J.HDU - 2457 DNA repair题意给你N个病毒串,然后给你一个长度为N的基因串,让你替换成没有病毒的基因串,求最小的替换次数(每次只能替换一个字符) 题解DP I,J I: 当前串的长度,J,结尾的位置 直接DP扫过去,用AC自动机构造出病毒的节点,然后开始构造,如果新的点和原来的串相同就 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,b);} int dp[1050][1050]; char buf[1500]; struct Trie{ int next[1100][4],fail[1010]; bool end[1010]; char s['Z'+1]; int root,L; int newnode(){ for(int i=0;i<4;i++) next[L][i]=-1; end[L++]=false; return L-1; } void init(){ L=0; s['A']=0;s['G']=1;s['T']=2;s['C']=3; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][s[buf[i]]]==-1) next[now][s[buf[i]]]=newnode(); now=next[now][s[buf[i]]]; } end[now]=true; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<4;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]])end[now]=true; for(int i=0;i<4;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void slove(int n){ memset(dp,inf,sizeof(dp)); dp[0][0]=0; for(int i=0;i<n;i++){ for(int j=0;j<L;j++){ if(dp[i][j]!=inf){ for(int k=0;k<4;k++){ int nex=next[j][k]; if(end[nex])continue; if(s[buf[i]]==k){ dp[i+1][nex]=min(dp[i+1][nex],dp[i][j]); } else{ dp[i+1][nex]=min(dp[i+1][nex],dp[i][j]+1); } } } } } int mi=inf; for(int i=0;i<L;i++){ if(dp[n][i]<mi)mi=dp[n][i]; } if(mi==inf)cout<<-1<<endl; else cout<<mi<<endl; } }; Trie ac; int n; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t=0; while(cin>>n){ if(n==0)break; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); cin>>buf; cout<<"Case "<<++t<<": "; int len=strlen(buf); ac.slove(len); } return 0; } K.ZOJ - 3228 Searching the String题意先给你一个字符串,然后给你若干个子串,0代表能够重叠,1代表不能重叠,求出如今母串的次数。 题解多一个推断的是假设这个子串与上次出现的次数大于子串长度的话。就代表这次不是重叠的了 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=20090717; const int maxn=600010; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} char buf[100010]; int ans[maxn][2]; struct Trie{ int next[maxn][26],deep[maxn],last[maxn]; int end[100010]; int root,L; int newnode(){ for(int i=0;i<26;i++) next[L][i]=-1; deep[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[],int id){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1) next[now][buf[i]-'a']=newnode(); deep[next[now][buf[i]-'a']]=deep[now]+1; now=next[now][buf[i]-'a']; } end[id]=now; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1) next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); for(int i=0;i<26;i++) if(next[now][i]==-1) next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void slove(char buf[]){ for(int i=0;i<L;i++){ ans[i][0]=ans[i][1]=0; last[i]=-1; } int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ now=next[now][buf[i]-'a']; int temp=now; while(temp!=root){ ans[temp][0]++; if(i-last[temp]>=deep[temp]){ ans[temp][1]++; last[temp]=i; } temp=fail[temp]; } } } }; Trie ac; int n; char s[10]; int flag[100010]; void neww(){ int n,cas = 1; while (scanf("%s",buf) != EOF) { scanf("%d",&n); ac.init(); for (int i = 0; i < n; i++) { scanf("%d%s",&flag[i],s); ac.insert(s,i); } ac.build(); ac.slove(buf); printf("Case %dn",cas++); for (int i = 0; i < n; i++) printf("%dn",ans[ac.end[i]][flag[i]]); printf("n"); } } int main() { neww(); return 0; } L.HDU - 3341 Lost‘s revenge题意给出N个模式串(len<=10)和一个目标长串(len<=40)求将目标串重新排列后所能包含的模式串个数 题解首先重排列,所以目标串中的ACGT个数不能变化 刚开始想开个五维数组来存取状态,但是空间会爆炸; 所以搜了一下发现可以用模拟进制来把 ACGT的个数用一个数字表达 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=15000; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} int dp[505][maxn]; struct Trie{ int next[505][4],fail[505],end[505]; int ok['Z']; int root,L; int newnode(){ for(int i=0;i<4;i++)next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0;ok['A']=0;ok['G']=1;ok['C']=2;ok['T']=3; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ int ch=ok[buf[i]]; if(next[now][ch]==-1){ next[now][ch]=newnode(); } now=next[now][ch]; }end[now]++; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<4;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); end[now]+=end[fail[now]]; for(int i=0;i<4;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } int slove(char buf[]){ int len=strlen(buf); int num[4]={0,0}; memset(dp,sizeof(dp)); for(int i=0;i<len;i++){ num[ok[buf[i]]]++; } dp[0][0]=0; int bit[4]; bit[0]=1; bit[1]=(num[0]+1); bit[2]=(num[1]+1)*(num[0]+1); bit[3]=(num[2]+1)*(num[1]+1)*(num[0]+1); for(int i=0;i<=num[0];i++) for(int j=0;j<=num[1];j++) for(int k=0;k<=num[2];k++) for(int l=0;l<=num[3];l++){ int nowsta=i*bit[0]+j*bit[1]+k*bit[2]+l*bit[3]; for(int p=0;p<L;p++){ if(dp[p][nowsta]!=inf){ for(int kk=0;kk<4;kk++){ if(i==num[0]&&kk==0)continue; else if(j==num[1]&&kk==1)continue; else if(k==num[2]&&kk==2)continue; else if(l==num[3]&&kk==3)continue; int nexsta=nowsta+bit[kk]; int nex=next[p][kk]; dp[nex][nexsta]=max(dp[nex][nexsta],dp[p][nowsta]+end[nex]); } } } } int ans=num[0]*bit[0]+num[1]*bit[1]+num[2]*bit[2]+num[3]*bit[3]; int ma=0; for(int i=0;i<L;i++)ma=max(dp[i][ans],ma); return ma; } }; char buf[45]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; int cnt=1; while(cin>>n){ if(n==0)break; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); cin>>buf; cout<<"Case "<<cnt++<<": "; cout<<ac.slove(buf)<<endl; } return 0; } M.HDU - 3247 Resource Archiver题意给定n个文本串,m个病毒串,文本串重叠部分可以合并,但合并后不能含有病毒串,问所有文本串合并后最短多长。 思路把病毒和文本出串塞入AC自动机中,然后把每个文本串的结点 和另一个文本串的结点的最短路求出来,在用状态DP求出每个点到另一个点之间的距离 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=998244353; const int maxn=60000+50; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} struct Trie{ int next[maxn][2],fail[maxn]; int end[maxn],dp[1025][11]; int mat[11][11]; int pos[11]; int dis[maxn]; int root,L; int cnt; int newnode(){ for(int i=0;i<2;i++)next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[],int id){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ int ch=buf[i]-'0'; if(next[now][ch]==-1){ next[now][ch]=newnode(); } now=next[now][ch]; } if(id==-1||end[now]==-1)end[now]=-1; else end[now]|=(1<<id); } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<2;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]]==-1)end[now]=-1; else end[now]|=end[fail[now]]; for(int i=0;i<2;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void bfs(int id){ queue<int>Q; Q.push(pos[id]); memset(dis,-1,sizeof(dis)); dis[pos[id]]=0; while(!Q.empty()){ int now=Q.front(); Q.pop(); for(int i=0;i<2;i++){ if(end[next[now][i]]>=0&&dis[next[now][i]]<0){ dis[next[now][i]]=dis[now]+1; Q.push(next[now][i]); } } } for(int i=0;i<cnt;i++) mat[id][i]=dis[pos[i]]; return; } void slove(int n){ pos[0]=0; cnt=1; for(int i=0;i<L;i++) if(end[i]>0)pos[cnt++]=i; for(int i=0;i<cnt;i++){ bfs(i); } for(int i=0;i<(1<<n);i++) for(int j=0;j<cnt;j++) dp[i][j]=inf; dp[0][0]=0; for(int i=0;i<(1<<n);i++) for(int j=0;j<cnt;j++) if(dp[i][j]!=inf){ for(int k=0;k<cnt;k++){ if(mat[j][k]<0)continue; dp[i|end[pos[k]]][k]=min(dp[i|end[pos[k]]][k],dp[i][j]+mat[j][k]); } } int ans=inf; for(int i=0;i<cnt;i++)ans=min(ans,dp[(1<<n)-1][i]); cout<<ans<<endl; return; } }; char buf[55000]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n,m; while(cin>>n>>m){ if(n==0&&m==0)break; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf,i); } for(int i=0;i<m;i++){ cin>>buf; ac.insert(buf,-1); } ac.build(); ac.slove(n); } return 0; } N.ZOJ - 3494 BCD Code题意跟数位DP的一题重复了 这里再做一次 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+9; const int maxn=2200; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} ll dp[300][maxn]; int num[300]; char nu[10][5]={"0000","0001","0010","0011","0100","0101","0110","0111","1000","1001"}; struct Trie{ int next[maxn][2],L; int newnode(){ for(int i=0;i<2;i++)next[L][i]=-1; end[L++]=false; return L-1; } void init(){ L=0; root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ int ch=buf[i]-'0'; if(next[now][ch]==-1){ next[now][ch]=newnode(); } now=next[now][ch]; } end[now]=true; } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<2;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]])end[now]=true; for(int i=0;i<2;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } ll dfs(int pos,int in,bool zero,bool limit){ if(pos==-1)return 1; if(dp[pos][in]!=-1&&!limit)return dp[pos][in]; int up=limit?num[pos]:9; ll ans=0; for(int i=0;i<=up;i++){ int now=in; if(zero&&i==0)ans=(ans+dfs(pos-1,in,zero&&i==0,limit&&i==up))%mod; else{ bool flag=0; for(int j=0;j<4;j++){ int ne=nu[i][j]-'0'; now=next[now][ne]; if(end[now]){ flag=1;break; } } if(!flag)ans=(ans+dfs(pos-1,now,limit&&i==up))%mod; } } if(!limit&&!zero)dp[pos][in]=ans; return ans; } ll Ac(char buf[]){ int len=strlen(buf); for(int i=0;i<len;i++){ num[i]=int(buf[len-1-i]-'0'); } return dfs(len-1,true,true); } }; char buf[22]; Trie ac; char a[250],b[250]; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; cin>>t; while(t--){ ac.init(); int n; cin>>n; memset(dp,sizeof(dp)); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); cin>>a>>b; int len=strlen(a); while(a[len-1]=='0'){ a[len-1]='9'; len--; } a[len-1]--; cout<<((ac.Ac(b)-ac.Ac(a)+mod)%mod)<<endl; } return 0; } O.HDU - 4758 Walk Through Squares题意给你一个n*m的网格,现在你要从(1,1)走到(n,m),每次只能向右走或者向下走,走完后会形成一个包含R,D的序列,这个序列必须要包含题目给出的两个字符串,问有多少种方案。 题解由于要从(1,m),所以这个形成的字符串包含R和D的数量是一定的。 现在考虑dp i j k sta,表示包含两种串的组合状态,走了i个D,走了j个R,走到了k这个AC自动机的节点的方案数,串1和串2的状态sta 然后dp一下就行了。复杂度为O(3×n×m×len(s1)×len(s2)) 按理说应该是N个D M个R 可是这样我就错了,换一下才AC。。。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=1010; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} int dp[110][110][210][4]; struct Trie{ int next[maxn][2],fail[maxn]; int end[maxn]; int ID['Z'+1]; int root,L; int newnode(){ for(int i=0;i<2;i++)next[L][i]=-1; end[L++]=false; return L-1; } void init(){ L=0; ID['R']=0;ID['D']=1; root=newnode(); } void insert(char buf[],int id){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ int ch=ID[buf[i]]; if(next[now][ch]==-1){ next[now][ch]=newnode(); } now=next[now][ch]; } end[now]=(1<<id); } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<2;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); end[now]|=end[fail[now]]; for(int i=0;i<2;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void slove(int n,int m){ memset(dp,sizeof(dp)); dp[0][0][0][0]=1; for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<L;k++) for(int sta=0;sta<(1<<2);sta++){ if(dp[i][j][k][sta]){ for(int p=0;p<2;p++){ if(p==0){//右 dp[i+1][j][next[k][p]][sta|end[next[k][p]]]+=dp[i][j][k][sta]; dp[i+1][j][next[k][p]][sta|end[next[k][p]]]%=mod; } else{ dp[i][j+1][next[k][p]][sta|end[next[k][p]]]+=dp[i][j][k][sta]; dp[i][j+1][next[k][p]][sta|end[next[k][p]]]%=mod; } } } } int ans=0; for(int i=0;i<L;i++){ ans+=dp[n][m][i][3]; ans%=mod; } cout<<ans<<endl; } }; char buf[110]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; ac.init(); for(int i=0;i<2;i++){ cin>>buf; ac.insert(buf,i); } ac.build(); ac.slove(n,m); } return 0; } P.HDU - 4511 小明系列故事――女友的考验题意中文题题解设dp i j 表示到第i个点,自动机状态到j的最小步数,注意的是因为我们是根据不合法的路径构造自动机的,所以我们是不能走到某一条路径的末尾的,根据这点来记录我们的终止条件 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=1010; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const double inf=1e20; int gcd(int a,b);} pp p[101]; double dp[55][1000]; double dis(pp a,pp b){ return sqrt((double)(1.0*a.first-b.first)*(double)(1.0*a.first-b.first)+(double)(1.0*a.second-b.second)*(double)(1.0*a.second-b.second)); } int n; struct Trie{ int next[maxn][55],fail[maxn]; int end[maxn]; int root,L; int newnode(){ for(int i=1;i<=n;i++)next[L][i]=-1; end[L++]=0; return L-1; } void init(){ L=0; root=newnode(); } void insert(int buf[],int k){ int now=root; for(int i=0;i<k;i++){ if(next[now][buf[i]]==-1){ next[now][buf[i]]=newnode(); } now=next[now][buf[i]]; } end[now]=1; } void build(){ queue<int>Q; fail[root]=root; for(int i=1;i<=n;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); end[now]|=end[fail[now]]; for(int i=1;i<=n;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void slove(){ for(int i=1;i<=n;i++)for(int j=0;j<L;j++)dp[i][j]=inf; dp[1][next[root][1]]=0; for(int i=1;i<n;i++) for(int j=0;j<L;j++) if(dp[i][j]!=inf){ for(int k=i+1;k<=n;k++){ int now=next[j][k]; if(end[now])continue; dp[k][now]=min(dp[k][now],dp[i][j]+dis(p[i],p[k])); } } double ans=inf; for(int i=0;i<L;i++)ans=min(ans,dp[n][i]); if(ans==inf)cout<<"Can not be reached!"<<endl; else printf("%.2fn",ans); } }; int buf[110]; Trie ac; int main() { /*std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0);*/ int m; while(cin>>n>>m){ if(n==0&&m==0)break; for(int i=1;i<=n;i++)cin>>p[i].first>>p[i].second; ac.init(); while(m--){ int k; cin>>k; for(int i=0;i<k;i++)cin>>buf[i]; ac.insert(buf,k); } ac.build(); ac.slove(); } return 0; } Q.附加题1 牛客网暑期ACM多校训练营(第九场)- Typing practice题意有n(n<=4)个长度为len的字符串,以及一个长度为len2的操作串。每一次你将选取操作串中长度为i(0<=i<=len2)的前缀,问你最少在这个前缀后加多少个字符,使得新字符串的后缀中能够至少出现这n个字符串中的一个。 题解因为题目中设计多个串的匹配一个长串的问题,我们可以考虑使用AC自动机进行处理。 #include<bits/stdc++.h> using namespace std; typedef long long ll; #define pp pair<int,int> const ll mod=1e9+7; const int maxn=450000; //const ll inf=0x3f3f3f3f3f3f3f3fLL; const int inf=0x3f3f3f3f; int gcd(int a,b);} struct Trie{ int next[maxn][26],fail[maxn]; bool end[maxn]; int ans[maxn]; vector<int>ve[maxn]; set<int>st; int root,L; int newnode(){ for(int i=0;i<26;i++)next[L][i]=-1; ans[L]=inf; end[L++]=false; return L-1; } void init(){ L=0; st.clear(); root=newnode(); } void insert(char buf[]){ int len=strlen(buf); int now=root; for(int i=0;i<len;i++){ if(next[now][buf[i]-'a']==-1){ next[now][buf[i]-'a']=newnode(); } now=next[now][buf[i]-'a']; } end[now]=true; ans[now]=0; st.insert(now); } void build(){ queue<int>Q; fail[root]=root; for(int i=0;i<26;i++) if(next[root][i]==-1)next[root][i]=root; else{ fail[next[root][i]]=root; Q.push(next[root][i]); } while(!Q.empty()){ int now=Q.front(); Q.pop(); if(end[fail[now]]){ end[now]=true; ans[now]=0; st.insert(now); } for(int i=0;i<26;i++) if(next[now][i]==-1)next[now][i]=next[fail[now]][i]; else{ fail[next[now][i]]=next[fail[now]][i]; Q.push(next[now][i]); } } } void slove(char buf[]){ for(int i=0;i<L;i++){ for(int j=0;j<26;j++){ ve[next[i][j]].push_back(i); } } queue<int>q; for(auto i:st){ q.push(i); } while(!q.empty()){ int now=q.front(); q.pop(); for(int i=0;i<ve[now].size();i++){ if(ans[ve[now][i]]>ans[now]+1){ ans[ve[now][i]]=min(ans[ve[now][i]],ans[now]+1); q.push(ve[now][i]); } } } int len=strlen(buf); stack<int>ss; int now=root; cout<<ans[now]<<endl; for(int i=0;i<len;i++){ if(buf[i]=='-'&&ss.empty()){ now=root; } else if(buf[i]=='-'){ now=ss.top(); ss.pop(); } else{ ss.push(now); now=next[now][buf[i]-'a']; } cout<<ans[now]<<endl; } } }; char buf[110000]; Trie ac; int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); std::cout.tie(0); int n; cin>>n; ac.init(); for(int i=0;i<n;i++){ cin>>buf; ac.insert(buf); } ac.build(); cin>>buf; ac.slove(buf); return 0; }
时间:2019-01-29 00:53:23
阅读(14)
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |