今天下午讨论了一下校赛的题，最终最终拍板，把校赛的题目定下来了。
然后今天A掉了4个AC自己主动机的题目。最终完毕了AC自己主动机专辑里面的15个题。至此AC自己主动机全然结束。
明天开启线段树专题。
。。。。
------------------------------------------------------------------------------------------------------------------------------------
1,，hdu-2457-DNA repair
题目：给出一些不合法的模式DNA串，给出一个原串，问最少须要改动多少个字符，使得原串中不包括非法串
做法：把病毒串做成一个trie树。
DP[i][j]:长度为i，在trie树上的状态为j。须要改变的最少的字符的个数。
dp[i][j]=dp[i-1][k]+转移费用。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
#define LL __int64
#define maxn 55
const int maxnode=55*21;
const int childnum=5;
const int mod=1000000007;
const int INF=99999999;
struct ac_tree
{int chd[maxnode][childnum];int val[maxnode];int fail[maxnode];int key[1<<11];int Q[maxnode];int ID[128];int sz;int dp[1100][maxnode];void init(){fail[0]=0;for(int i=0;i<childnum;i++){ID[i]=i;}ID['A']=1;ID['G']=2;ID['C']=3;ID['T']=4;}void reset(){memset(chd,0,sizeof(chd));sz=1;}void insert(char str[],int k){int p=0;int len=strlen(str);for(int i=0;i<len;i++){int c=ID[str[i]];if(!chd[p][c]){memset(chd[sz],0,sizeof(chd[sz]));val[sz]=0;chd[p][c]=sz++;}p=chd[p][c];}val[p]=k;}void ac_build(){int *s=Q,*e=Q;for(int i=1;i<childnum;i++){if(chd[0][i]){fail[chd[0][i]]=0;*e++=chd[0][i];}}while(s!=e){int u=*s++;if(val[fail[u]])val[u]+=val[fail[u]];for(int i=1;i<childnum;i++){int &v=chd[u][i];if(v){*e++=v;fail[v]=chd[fail[u]][i];// val[v]=(val[v]+val[fail[v]]);}else v=chd[fail[u]][i];}}}int work(char str[]){int len=strlen(str);int i,j,k;for(i=0;i<=len;i++)for(j=0;j<sz;j++)dp[i][j]=INF;dp[0][0]=0;int cr,x;for(i=0;i<len;i++){for(j=0;j<sz;j++){if(dp[i][j]==INF)continue;for(k=1;k<childnum;k++){cr=chd[j][k];if(val[cr])continue;x=dp[i][j];if(k!=ID[str[i]])x++;dp[i+1][cr]=min(dp[i+1][cr],x);}}}int maxx=INF;for(j=0;j<sz;j++){maxx=min(maxx,dp[len][j]);}if(maxx==INF)cout<<"-1"<<endl;else cout<<maxx<<endl;}
}AC;
char tmp[1550];
int main()
{AC.init();int n,m,k,x;int T;T=0;while(~scanf("%d",&n)&&(n)){T++;AC.reset();for(int i=1;i<=n;i++){scanf("%s",tmp);AC.insert(tmp,1);}AC.ac_build();scanf("%s",tmp);printf("Case %d: ",T);AC.work(tmp);}return 0;
}2，zoj-3228-Searching the String
题目大意：给出一个字符串和若干个单词。问这些单词在字符串里面出现了多少次。单词前面为0表示这个单词可重叠出现。1为不可重叠出现。
做法： 可重叠的非常优点理，就是AC自己主动机处理。不可重叠的就记录下上次这个单词出现的位置。假设上次出现的位置加上这个单词的长度小于等于当前位置的话，那么这个单词的次数就加一。否则就不加。
注意：可能存在两个字符串相等，比較坑爹。。。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
#define LL __int64
#define maxn 55
const int maxnode=6*110000;
const int childnum=27;
const int mod=1000000007;
const int INF=99999999;
struct ac_tree
{int chd[maxnode][childnum];int val[maxnode][2];int fail[maxnode];int last[maxnode];int num[maxnode][2];int *ans[maxnode];int key[1<<11];int Q[maxnode];int ID[128];int sz;void init(){fail[0]=0;for(int i=0;i<childnum;i++){ID[i+'a']=i+1;}}void reset(){memset(chd,0,sizeof(chd));memset(num,0,sizeof(num));sz=1;}void insert(char str[],int k,int tt){int p=0;int len=strlen(str);for(int i=0;i<len;i++){int c=ID[str[i]];if(!chd[p][c]){memset(chd[sz],0,sizeof(chd[sz]));val[sz][tt]=0;chd[p][c]=sz++;}p=chd[p][c];}val[p][tt]=len;last[p]=-1;ans[k]=&num[p][tt];}void ac_build(){int *s=Q,*e=Q;for(int i=1;i<childnum;i++){if(chd[0][i]){fail[chd[0][i]]=0;*e++=chd[0][i];}}while(s!=e){int u=*s++;//if(val[fail[u]])val[u]+=val[fail[u]];for(int i=1;i<childnum;i++){int &v=chd[u][i];if(v){*e++=v;fail[v]=chd[fail[u]][i];// val[v]=(val[v]+val[fail[v]]);}else v=chd[fail[u]][i];}}}int work(char str[],int n){int len=strlen(str);int root=0,key,tp,x;for(int i=0;i<len;i++){tp=ID[str[i]];root=chd[root][tp];key=root;while(key!=0){if(val[key][0]!=0)num[key][0]++;if(val[key][1]!=0){if(last[key]<=i-val[key][1]){num[key][1]++;last[key]=i;}}key=fail[key];}}for(int i=1;i<=n;i++)printf("%d\n",*ans[i]);puts("");}
}AC;
char tmp[1550];
char as[110000];
int main()
{AC.init();int n,m,k,x;int T;T=0;while(~scanf("%s",as)){T++;AC.reset();scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d %s",&k,tmp);AC.insert(tmp,i,k);}AC.ac_build();printf("Case %d\n",T);AC.work(as,n);}return 0;
}3，hdu-3341-Lost's revenge
抄的解题报告，感觉说的非常具体。我就不赘余了。
。
题意：给出一些病毒串，一个原串，问怎么调整原串的顺序使得跟最多的病毒串匹配
抄解题报告： 自己主动机+DP。设主串有na个A、nc个C、ng个G、nt个T，于是题意转化为用na个A、 nc个C、ng个G、nt个T生成一个新串，使模式串匹配次数最大。
先将模式串生成自己主动机 〔trie图〕，然后在这上面进行DP。状态可表示为dp[d,s]，d为自己主动机状态。 s表示由ma个A、mc个C、mg个G、mt个T的生成串 〔s可表示为ma*(nc+1)*(ng+1)*(nt+1)+mc*(ng+1)*(nt+1)+mg*(nt+1)+mt〕。 转移为O(4)，总复杂度O(500*11^4*4) 那种表示方法就是变进制吧 直接DP(root,s)会超时 Qinz说这题卡时紧 我用他的那种dfs才干过。他是先dfs枚举出状态，然后对这个状态递推计算。好快 比較奇妙，不用管顺序的，就记录个数
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
#define LL __int64
#define maxn 55
const int maxnode=51*10;
const int childnum=5;
const int mod=1000000007;
const int INF=99999999;
struct ac_tree
{int chd[maxnode][childnum];int val[maxnode];int fail[maxnode];int Q[maxnode];int ID[128];int sz;int dp[maxnode][14642];void init(){fail[0]=0;for(int i=0;i<childnum;i++){ID[i+'a']=i+1;}ID['A']=1;ID['T']=2;ID['G']=3;ID['C']=4;}void reset(){memset(chd,0,sizeof(chd));memset(val,0,sizeof(val));sz=1;}void insert(char str[],int k){// cout<<str<<endl;int p=0;int len=strlen(str);for(int i=0;i<len;i++){int c=ID[str[i]];if(!chd[p][c]){memset(chd[sz],0,sizeof(chd[sz]));val[sz]=0;chd[p][c]=sz++;}p=chd[p][c];}val[p]+=k;//cout<<p<<" "<<val[p]<<endl;}void ac_build(){int *s=Q,*e=Q;for(int i=1;i<childnum;i++){if(chd[0][i]){fail[chd[0][i]]=0;*e++=chd[0][i];}}while(s!=e){int u=*s++;if(val[fail[u]])val[u]+=val[fail[u]];for(int i=1;i<childnum;i++){int &v=chd[u][i];if(v){*e++=v;fail[v]=chd[fail[u]][i];// val[v]=(val[v]+val[fail[v]]);}else v=chd[fail[u]][i];}}}int work(char str[]){int num[5];memset(num,0,sizeof(num));int len=strlen(str);for(int i=0;i<len;i++)num[ID[str[i]]]++;dp[0][0]=0;int tai,cr;int sum[6];sum[5]=1;sum[4]=num[4]+1;sum[3]=(num[3]+1)*sum[4];sum[2]=(num[2]+1)*sum[3];sum[1]=(num[1]+1)*sum[2];int a[5],i,j;int pt;memset(dp,-1,sizeof(dp));dp[0][0]=0;for(a[1]=0;a[1]<=num[1];a[1]++)for(a[2]=0;a[2]<=num[2];a[2]++)for(a[3]=0;a[3]<=num[3];a[3]++)for(a[4]=0;a[4]<=num[4];a[4]++){if(a[1]+a[2]+a[3]+a[4]>=len)break;tai=0;for(i=1;i<=4;i++)tai+=a[i]*sum[i+1];for(i=0;i<sz;i++){if(dp[i][tai]==-1)continue;for(j=1;j<childnum;j++){if(a[j]+1>num[j])continue;cr=chd[i][j];pt=tai+sum[j+1];// if(dp[cr][pt]==-1)dp[cr][pt]=dp[i][tai];dp[cr][pt]=max(dp[cr][pt],dp[i][tai]+val[cr]);// cout<<i<<" "<<j<<"->"<<cr<<" "<<pt<<" "<<dp[cr][pt]<<endl;}}}pt=num[1]*sum[2]+num[2]*sum[3]+num[3]*sum[4]+num[4];int maxx=-1;for(i=0;i<sz;i++){maxx=max(maxx,dp[i][pt]);}cout<<maxx<<endl;}
}AC;
char tmp[1550];
char as[110000];
int main()
{AC.init();int n,m,k,x;int T;T=0;while(~scanf("%d",&n)&&n){T++;AC.reset();for(int i=1;i<=n;i++){scanf("%s",tmp);AC.insert(tmp,1);}AC.ac_build();scanf("%s",as);printf("Case %d: ",T);AC.work(as);}return 0;
}4，hdu-3247-Resource Archiver
题意：
给你 n 个串。和 m 个病毒串。要把这 n 个串
连起来来，能够重叠，但不能包括 m 个病毒串
中的随意一个。求把 n 个串连起来的最小长度。 做法：这个题目憋了我非常长时间，一直不知道怎么样处理。后来经过翻阅博客。最终悟出来点。
把病毒串和非病毒串都标记在trie树上处理。然后病毒串的地方标记为病毒串，非病毒串的地方标记为是哪一个串。
状态压缩一下。
然后从每一个非病毒串的结尾開始bfs。
map[i][j]:从i字符串的结尾。到j字符串的结尾的最短路径是多少。
然后就能够DP了。
dp[i][j]:已用的字符串为i状态，在trie树上的点为j状态。的最短路径。
#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<string.h>
#include<math.h>
using namespace std;
#define LL __int64
#define maxn 205
const int maxnode=100001;
const int childnum=3;
const int mod=1000000007;
const int INF=99999999;
struct list
{int st;int x;
}pp,qq;
struct ac_tree
{int chd[maxnode][childnum];int val[maxnode];int fail[maxnode];int Q[maxnode];int var[maxnode];int vis[maxnode];int dist[maxnode];int st[maxn];int ID[128];int sz;int maps[maxn][maxn];int ns;int dp[1<<11][maxn];void init(){fail[0]=0;for(int i=0;i<childnum;i++){ID[i+'a']=i+1;}ID['0']=1;ID['1']=2;}void reset(){memset(chd,0,sizeof(chd));memset(val,0,sizeof(val));memset(var,0,sizeof(var));memset(maps,-1,sizeof(maps));sz=1;}void insert(char str[],int k,int ps){// cout<<str<<endl;int p=0;int len=strlen(str);for(int i=0;i<len;i++){int c=ID[str[i]];if(!chd[p][c]){memset(chd[sz],0,sizeof(chd[sz]));val[sz]=0;chd[p][c]=sz++;}p=chd[p][c];}if(ps==0){val[p]=k;var[p]=0;}else var[p]=1;//cout<<p<<" "<<val[p]<<endl;}void ac_build(){int *s=Q,*e=Q;for(int i=1;i<childnum;i++){if(chd[0][i]){fail[chd[0][i]]=0;*e++=chd[0][i];}}while(s!=e){int u=*s++;//if(val[fail[u]]==-1)val[u]=-1;for(int i=1;i<childnum;i++){int &v=chd[u][i];if(v){*e++=v;fail[v]=chd[fail[u]][i];val[v]=(val[v]|val[fail[v]]);var[v]=(var[v]|var[fail[v]]);}else v=chd[fail[u]][i];}}}int bfs(int u){queue<int>que;while(!que.empty())que.pop();int x=st[u];que.push(x);memset(dist,-1,sizeof(dist));dist[x]=0;while(!que.empty()){x=que.front();que.pop();for(int i=1;i<childnum;i++){int y=chd[x][i];if(var[y])continue;if(dist[y]<0){dist[y]=dist[x]+1;que.push(y);}}}for(int i=0;i<ns;i++){maps[u][i]=dist[st[i]];//cout<<u<<"->"<<i<<"="<<maps[u][i]<<endl;}}int work(int n){st[0]=0;ns=1;for(int i=0;i<sz;i++)if(val[i]){st[ns++]=i;//cout<<ns-1<<" "<<val[st[ns-1]]<<endl;}for(int i=0;i<ns;i++)bfs(i);memset(dp,-1,sizeof(dp));dp[0][0]=0;int cr;for(int i=0;i<(1<<n);i++){for(int j=0;j<ns;j++){if(dp[i][j]<0)continue;for(int k=0;k<ns;k++){if(maps[j][k]<0)continue;cr=i|val[st[k]];if(dp[cr][k]==-1)dp[cr][k]=dp[i][j]+maps[j][k];else dp[cr][k]=min(dp[cr][k],dp[i][j]+maps[j][k]);// cout<<cr<<" "<<k<<" "<<dp[cr][k]<<endl;}}}int minn=-1;cr=(1<<n)-1;for(int i=0;i<ns;i++){if(dp[cr][i]==-1)continue;if(minn<0)minn=dp[cr][i];minn=min(minn,dp[cr][i]);}cout<<minn<<endl;}}AC;
char tmp[1550];
int main()
{AC.init();int n,m,k,x;int T;T=0;while(~scanf("%d%d",&n,&m)&&(n||m)){AC.reset();for(int i=1;i<=n;i++){scanf("%s",tmp);AC.insert(tmp,1<<(i-1),0);}for(int i=1;i<=m;i++){scanf("%s",tmp);AC.insert(tmp,1,1);}AC.ac_build();AC.work(n);}return 0;
}