首页 > 代码库 > ZOJ 3817Chinese Knot(The 2014 ACM-ICPC Asia Mudanjiang Regional First Round)
ZOJ 3817Chinese Knot(The 2014 ACM-ICPC Asia Mudanjiang Regional First Round)
思路： 将4个串每个串都反向这样得到新的四个串一共8个串，对于母串每个位置检测这个串能不能放进去，hs或者后缀数组都可以。然后dp[i][j] (0<i<len 0<=j<8)表示长度为i以第j个串结尾能不能到达，如果能 那么 就可以i+1位置利用原来处理出来的来转移。要注意开头结尾即可。
注意：以第i个串结尾 那么下个串 就不能用第i个串的反向串。
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<vector>#include<queue>#include<map>#include<set>#include<time.h>#include<string>#define REP(i,n) for(int i=0;i<n;++i)#define REP1(i,a,b) for(int i=a;i<=b;++i)#define REP2(i,a,b) for(int i=a;i>=b;--i)#define MP make_pair#define LL long long#define ULL unsigned long long#define X first#define Y second#define MAXN 100050using namespace std;int pre[MAXN][8];bool bo[MAXN][8];bool dp[MAXN][8];bool ed[MAXN][8];ULL hs[9][MAXN];ULL p[MAXN];int id[8][MAXN];char s[9][MAXN];int len[9];void makehs(int id){ hs[id][0]=1; for(int i=1;i<=len[id];++i) hs[id][i]=hs[id][i-1]*31+s[id][i-1]-‘a‘+1;}ULL geths(int id,int l,int r){ l--; return hs[id][r]-hs[id][l]*p[r-l];}int q[MAXN];int tail;void out(int cid,int l,int r){ for(int i=r;i>=l;--i) q[tail++]=id[cid][i];}int main() { p[0]=1; for(int i=1;i<MAXN;++i)p[i]=p[i-1]*31; int tt,n,m; scanf("%d",&tt); while(tt--) { scanf("%d%d",&n,&m); memset(bo,0,sizeof(bo)); memset(dp,0,sizeof(dp)); memset(ed,0,sizeof(ed)); memset(pre,-1,sizeof(pre)); int cid=1; for(int i=0;i<4;++i){ scanf(" %s",s[i*2]); len[i*2]=len[i*2+1]=strlen(s[i*2]); for(int j=0;j<len[i*2];++j) { s[i*2+1][j]=s[i*2][len[i*2]-j-1]; id[i*2][j]=cid; id[i*2+1][len[i*2]-j-1]=cid++; } makehs(i*2); makehs(i*2+1); } scanf(" %s",s[8]); len[8]=strlen(s[8]); makehs(8); //整串转移 for(int i=0;i<m;++i){ for(int j=0;j<8;++j){ if(i+len[j]<=m){ ULL tmp1=geths(8,i+1,i+len[j]); ULL tmp2=geths(j,1,len[j]); if(tmp1!=tmp2)continue; bo[i][j]=true; } } } //开头 for(int i=0;i<m;++i){ for(int j=0;j<8;++j){ if(len[j]>i){ ULL tmp1=geths(8,1,i+1); ULL tmp2=geths(j,len[j]-i,len[j]); if(tmp1!=tmp2)continue; dp[i][j]=true; } } } //结尾 for(int i=0;i<m;++i){ for(int j=0;j<8;++j){ if(len[j]>len[8]-i){ ULL tmp1=geths(8,i+1,len[8]); ULL tmp2=geths(j,1,len[8]-i); if(tmp1!=tmp2)continue; ed[i][j]=true; } } } int pos=-1,posx,flag=0,fol; //转移 for(int i=0;i<m;++i){ for(int j=0;j<8;++j){ if(!dp[i][j])continue; if(i==m-1){ pos=i; posx=j; flag=1; break; } for(int k=0;k<8;++k){ if((j^k)==1)continue; if(!ed[i+1][k])continue; pos=i; posx=j; fol=k; flag=1; break; } for(int k=0;k<8;++k){ if((j^k)==1)continue; if(!bo[i+1][k])continue; dp[i+len[k]][k]=true; pre[i+len[k]][k]=j; } } if(flag)break; } if(flag==0) { puts("No solution!"); continue; } tail=0; if(pos!=m-1){ out(fol,0,m-pos-2); } while(posx!=-1){ if(len[posx]>pos+1)out(posx,len[posx]-pos-1,len[posx]-1); else out(posx,0,len[posx]-1); int tmpx=posx; posx=pre[pos][posx]; pos=pos-len[tmpx]; } for(int i=tail-1;i>0;--i)printf("%d ",q[i]); printf("%d\n",q[0]); } return 0;}/*13 3abcabcabcabcbaa*/
ZOJ 3817Chinese Knot(The 2014 ACM-ICPC Asia Mudanjiang Regional First Round)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。