【NOIP2004】虫食算（暴力）

#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #define MAXN 90 using namespace std; int n,abc[MAXN],p; char a[MAXN],b[MAXN],c[MAXN],word[MAXN]; bool used[MAXN]; void print() { for(int i='A';i<'A'+n-1;i++) printf("%d ",abc[i]); printf("%d\n",abc['A'+n-1]); } bool check() { int jw=0; for(int i=n-1;i>=0;i--) { int x=abc[(int)a[i]],y=abc[(int)b[i]],z=abc[(int)c[i]]; if(x!=-1&&y!=-1&&z!=-1) { if(jw==-1) { if(((x+y)%n==z)||(x+y+1)%n==z) jw=(x+y)/n; else return 0; } else { if((x+y+jw)%n==z) jw=(x+y+jw)/n; else return 0; } } else if(x!=-1&&y!=-1) { int sum=x+y,f=-1; if(sum>=n){sum-=n;f=1;} else f=0; if(jw!=1&&!used[sum]){jw=f;continue;} sum=x+y+1; if(sum>=n){sum-=n;f=1;} else f=0; if(!used[sum]){jw=f;continue;} return 0; } else if(x!=-1&&z!=-1) { int sum=z-x,f=-1; if(sum<0){sum+=n;f=1;} else f=0; if(jw!=1&&!used[sum]){jw=f;continue;} sum=z-x-1; if(sum<0){sum+=n;f=1;} else f=0; if(sum>=0&&!used[sum]){jw=f;continue;} return 0; } else if(y!=-1&&z!=-1) { int sum=z-y,f=-1; if(sum<0){sum+=n;f=1;} else f=0; if(jw!=1&&!used[sum]){jw=f;continue;} sum=z-y-1; if(sum<0){sum+=n;f=1;} else f=0; if(sum>=0&&!used[sum]){jw=f;continue;} return 0; } else jw=-1; } if(jw!=1)return 1; return 0; } void dfs(int x) { if(x==n) { print(); exit(0); } for(int i=0;i<n;i++) if(!used[i]) { used[i]=1; abc[(int)word[x]]=i; if(!check()) { used[i]=0; abc[(int)word[x]]=-1; continue; } dfs(x+1); used[i]=0; abc[(int)word[x]]=-1; } } int main() { cin>>n>>a>>b>>c; for(int i=n-1;i>=0;i--) { if(!used[(int)a[i]]) { used[(int)a[i]]=1; word[p++]=a[i]; } if(!used[(int)b[i]]) { used[(int)b[i]]=1; word[p++]=b[i]; } if(!used[(int)c[i]]) { used[(int)c[i]]=1; word[p++]=c[i]; } } memset(used,0,sizeof(used)); memset(abc,-1,sizeof(abc)); dfs(0); return 0; }

另一种做法：做法2