首页 > 代码库 > atitit.android模拟器使用报告
atitit.android模拟器使用报告
今天起得比较晚,又浪费了点时间,真可耻。。
下午又为校赛出了俩题,至此,校赛的四道题目已经完毕。又检查了一番,没有错误,就等待着明天的汇总了~。
AC自动机的题目今天就刷了三道,还是没有完成之前的目标。现在vj也进不去了,想通宵,都不给机会~~
只能等明天再刷完了,拖延不是一个好习惯。
----------------------------------------------------------------------------------------------------------
1,hdu-4511-小明系列故事――女友的考验
抢了CZ的FB,心里很高兴,哈哈
AC自动机越来越模板了,就先创建非法路径的自动机。然后再树上求1点到n点的最短路。我当时没有注意要“只能走到比当前所在点编号大的位置; ”的条件,错了N次,伤心。。
#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=110*5; const int childnum=55; const int mod=1000000007; const int INF=99999999; struct list { double x; double y; }node[maxn]; struct listt { int p; int t; double dis; friend bool operator <(const listt &a,const listt &b) { return a.dis>b.dis; } }pp,qq; double dist(int x,int y) { double xx,yy; xx=node[x].x-node[y].x; yy=node[x].y-node[y].y; double sum=xx*xx+yy*yy; return 1.0*sqrt(1.0*sum); } priority_queue<listt>que; 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 vis[maxn][maxnode]; void init() { fail[0]=0; for(int i=0;i<childnum;i++) { ID[i]=i; } } void reset() { memset(chd,0,sizeof(chd)); sz=1; } void insert(vector<int>vec,int k) { int p=0; int len=vec.size(); for(int i=0;i<len;i++) { int c=ID[vec[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 word(int n) { while(!que.empty())que.pop(); memset(vis,0,sizeof(vis)); pp.p=1; pp.t=chd[0][1]; pp.dis=0.0; que.push(pp); int cr; vis[1][pp.t]=1; while(!que.empty()) { pp=que.top(); que.pop(); // cout<<"____________"<<endl; // cout<<pp.p<<endl; if(pp.p==n) { printf("%.2f\n",pp.dis); return 0; } for(int i=pp.p+1;i<=n;i++) { cr=chd[pp.t][i]; if(i==pp.p)continue; if(val[cr])continue; //if(vis[i][cr])continue; // cout<<pp.p<<" "<<i<<" "<<cr<<endl; vis[i][cr]=1; qq.p=i; qq.t=cr; qq.dis=1.0*pp.dis+1.0*dist(pp.p,qq.p); que.push(qq); } } cout<<"Can not be reached!"<<endl; } }AC; char temp[155]; int main() { AC.init(); int n,m,k,x; int T; while(~scanf("%d%d",&n,&m)) { if(!(n||m))break; for(int i=1;i<=n;i++) { scanf("%lf%lf",&node[i].x,&node[i].y); } AC.reset(); vector<int>vec; for(int i=1;i<=m;i++) { vec.clear(); scanf("%d",&k); while(k--) { scanf("%d",&x); vec.push_back(x); } AC.insert(vec,1); } AC.ac_build(); AC.word(n); } return 0; }
2,hdu-4758-Walk Through Squares
1.对自动机上每个状态dp,dp[a][b][c][d]表示经过了a个字符,匹配了b个R,在c这个状态,d是4进制数,表示是否经过串1和串2
也就是一个树上DP,想好状态转移方程就好了。
#include<stdio.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> using namespace std; #define LL int const int maxnode=101*2; const int childnum=2; 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[104][104][maxnode][4]; void init() { fail[0]=0; for(int i=0;i<childnum;i++) { ID[i+‘a‘]=i; } ID[‘R‘]=0;ID[‘D‘]=1; } 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=0;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=0;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 word(int n,int m) { memset(dp,0,sizeof(dp)); dp[0][0][0][0]=1; int cr; int t; for(int i=0;i<=n;i++) { for(int j=0;j<=m;j++) { for(int k=0;k<sz;k++) { for(int z=0;z<4;z++) { if(dp[i][j][k][z]==0)continue; // dp[i][j][k][z]%=mod; // cout<<i<<" "<<j<<" "<<k<<" "<<z<<endl; cr=chd[k][0]; t=z|val[cr]; dp[i+1][j][cr][t]+=dp[i][j][k][z]; dp[i+1][j][cr][t]%=mod; cr=chd[k][1]; t=z|val[cr]; dp[i][j+1][cr][t]+=dp[i][j][k][z]; dp[i][j+1][cr][t]%=mod; } } } } int ans=0; for(int i=0;i<sz;i++) { ans+=dp[n][m][i][3]; ans%=mod; } ans=ans%mod; cout<<ans<<endl; } }AC; char temp[155]; int main() { AC.init(); int n,m,k; int T; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&m); AC.reset(); for(int i=1;i<=2;i++) { scanf("%s",temp); AC.insert(temp,(1<<(i-1))); } AC.ac_build(); AC.word(n,m); } return 0; }
3,hdu-4057- Rescue the Rabbit
dp[i][j][k],表示长度为i的串,位于Trie上的状态j,模式串的状态为k的最大价值。
状态压缩一下,就变成了普通的树上DP了,还需要滚动数组压缩一下空间。
#include<stdio.h> #include<algorithm> #include<iostream> #include<stdlib.h> #include<string.h> using namespace std; const int maxnode=101*10; const int childnum=4; const int mod=20090717; 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[2][maxnode][1<<10]; void init() { fail[0]=0; for(int i=0;i<childnum;i++) { ID[i+‘a‘]=i; } ID[‘A‘]=0;ID[‘T‘]=1; ID[‘G‘]=2;ID[‘C‘]=3; } void reset() { memset(chd,0,sizeof(chd)); sz=1; } void insert(char str[],int k,int d) { key[k]=d; 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=0;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=0;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 word(int n,int m) { int s=0; int l=1; int tai=(1<<m); int cr,tr; memset(dp,0,sizeof(dp)); dp[0][0][0]=1; for(int i=0;i<n;i++) { l=1-s; memset(dp[l],0,sizeof(dp[l])); // cout<<"__"<<endl; for(int j=0;j<sz;j++) { for(int k=0;k<tai;k++) { if(dp[s][j][k]==0)continue; //cout<<j<<" "<<k<<endl; for(int z=0;z<childnum;z++) { cr=chd[j][z]; // cout<<j<<"+"<<z<<"="<<cr<<endl; tr=val[cr]|k; dp[l][cr][tr]=1; } } } s=l; } int maxx=-1; int tt=0; for(int j=0;j<sz;j++) { for(int k=0;k<tai;k++) { if(dp[s][j][k]==0)continue; // cout<<j<<" "<<k<<endl; tt=0; for(int i=0;i<m;i++) { if(k&(1<<i))tt+=key[1<<i]; } maxx=max(tt,maxx); } } if(maxx<0)cout<<"No Rabbit after 2012!"<<endl; else cout<<maxx<<endl; } }AC; char temp[155]; int main() { AC.init(); int n,m,k; while(~scanf("%d%d",&n,&m)) { AC.reset(); for(int i=1;i<=n;i++) { scanf("%s %d",temp,&k); AC.insert(temp,(1<<(i-1)),k); } AC.ac_build(); AC.word(m,n); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。