P1092 虫食算

xiaoxiao2021-02-28  116

从低位开始枚举,若该列已填满进行判断,填了两个数进行计算,否则进行搜索。 引入邻接表可以跑得更快。 一开始第九个点总是T,尝试了倒着取数,但反而跑得更慢。因此将程序中的if和else有选择性地换了一下,爆了几发OJ,最后 在O2开关的帮助下 成功骗自己A掉了这题 搞笑代码: #prag\ ma GC\ C opti\ mize("O\ 2") #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cstdlib> using namespace std; #define rep(i,j,k) for(i=j;i<=k;++i) #define per(i,j,k) for(i=j;i>=k;--i) #define ll long long #define db double #define mkp(x,y) make_pair(x,y) #define pii pair<int,int> #define X first #define Y second int n,a1[26],a2[26],a3[26],c[26],L[26],R[26]; bool b[26]; void read(int a[]){ char s[27];scanf("%s",s); int i;per(i,n-1,0)a[i]=s[i]-'A'; } void del(int x){ R[L[x]]=R[x];L[R[x]]=L[x]; } void add(int x){ R[L[x]]=L[R[x]]=x; } void DFS(int k,bool flg){ if(k<0){ if(flg)return; int i;rep(i,0,n-1)printf("%d ",c[i]);puts("");exit(0); } bool flg2=0;int x,y,z; if((x=c[a1[k]])>=0&&(y=c[a2[k]])>=0){ z=x+y+flg; if(z>=n)z-=n,flg2=1; if((c[a3[k]])>=0){ if(c[a3[k]]==z)DFS(k-1,flg2); else return; } else{ if(b[z])return; b[c[a3[k]]=z]=1;del(z); DFS(k-1,flg2); b[z]=0;c[a3[k]]=-1;add(z); } /*if((c[a3[k]])<0){ if(b[z])return; b[c[a3[k]]=z]=1;del(z); DFS(k-1,flg2); b[z]=0;c[a3[k]]=-1;add(z); } else{ if(c[a3[k]]==z)DFS(k-1,flg2); else return; }*/ return; } else if((z=c[a3[k]])>=0){ /*if((x=c[a1[k]])>=0){ z-=flg; if(x<=z){ if(b[y=z-x])return; b[c[a2[k]]=y]=1;del(y); DFS(k-1,0); b[y]=0;c[a2[k]]=-1;add(y); } else{ if(b[y=z+n-x])return; b[c[a2[k]]=y]=1;del(y); DFS(k-1,1); b[y]=0;c[a2[k]]=-1;add(y); } return; }*/ if((x=c[a1[k]])>=0){ z-=flg; if(x>z){ if(b[y=z+n-x])return; b[c[a2[k]]=y]=1;del(y); DFS(k-1,1); b[y]=0;c[a2[k]]=-1;add(y); } else{ if(b[y=z-x])return; b[c[a2[k]]=y]=1;del(y); DFS(k-1,0); b[y]=0;c[a2[k]]=-1;add(y); } return; } if((y=c[a2[k]])>=0){ z-=flg; /* if(y>z){ if(b[x=z+n-y])return; b[c[a1[k]]=x]=1;del(x); DFS(k-1,1); b[x]=0;c[a1[k]]=-1;add(x); } else{ if(b[x=z-y])return; b[c[a1[k]]=x]=1;del(x); DFS(k-1,0); b[x]=0;c[a1[k]]=-1;add(x); } */ if(y<=z){ if(b[x=z-y])return; b[c[a1[k]]=x]=1;del(x); DFS(k-1,0); b[x]=0;c[a1[k]]=-1;add(x); } else{ if(b[x=z+n-y])return; b[c[a1[k]]=x]=1;del(x); DFS(k-1,1); b[x]=0;c[a1[k]]=-1;add(x); } return; } } int i; if((c[a1[k]])>=0){ for(i=L[n];i!=n+1;i=L[i]){ b[c[a2[k]]=i]=1;del(i);DFS(k,flg); b[i]=0;add(i); } c[a2[k]]=-1; } else{ for(i=L[n];i!=n+1;i=L[i])if(!b[i]){ b[c[a1[k]]=i]=1;del(i);DFS(k,flg); b[i]=0;add(i); } c[a1[k]]=-1; } } int main(){ scanf("%d",&n);read(a1);read(a2);read(a3); memset(c,-1,sizeof c); int i; per(i,n-1,0)L[R[i]=i+1]=i; R[L[0]=n+1]=0; DFS(n-1,0); return 0; }
转载请注明原文地址: https://www.6miu.com/read-62861.html

最新回复(0)