#include<iostream> #include<cstdio> #include<cstdlib> #include<ctime> #include<algorithm> #include<map> using namespace std; int n,cnt; map<char,int>m; char ch[26]={‘A‘,‘B‘,‘C‘,‘D‘,‘E‘,‘F‘,‘G‘,‘H‘,‘I‘,‘J‘,‘K‘,‘L‘,‘M‘,‘N‘,‘O‘,‘P‘,‘Q‘,‘R‘,‘S‘,‘T‘,‘U‘,‘V‘,‘W‘,‘X‘,‘Y‘,‘Z‘}; char s1[30],s2[30],s3[30]; int a[30],b[30],c[30],d[30]; bool check() { int tmp=0; for(int i=n-1;i>=0;i--) { c[i]=(m[s1[i]]+m[s2[i]]+tmp)%n; tmp=(m[s1[i]]+m[s2[i]]+tmp); tmp/=n; if(c[i]!=m[s3[i]]) return false; } return true; } int main() { scanf("%d",&n); scanf("%s",s1);scanf("%s",s2);scanf("%s",s3); for(int i=0;i<n;i++) a[i]=i; while(++cnt) { if(cnt>5000000) break; random_shuffle(a,a+n); for(int i=0;i<n;i++) m[ch[i]]=a[i]; if(check()) break; } for(int i=0;i<n;i++) printf("%d ",m[ch[i]]); return 0; }
/* 嗯...倒着搜，一列一列的搜 边搜边剪枝。 */ #include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #define N 27 using namespace std; int n,m,ans,cnt,tmp; char s1[N],s2[N],s3[N]; int match[N]; bool vis[N]; void dfs(int use,bool flag=false) { if(use==n) { if(!flag) { for(int i=0;i<n;i++) printf("%d ",match[i]); exit(0); } else return; } for(int k=n-2-use;k>=0;k--) if(match[s1[k]]!=-1 && match[s2[k]]!=-1 && match[s3[k]]!=-1 && (match[s1[k]]+match[s2[k]])%n!=match[s3[k]] && (1+match[s1[k]]+match[s2[k]])%n!=match[s3[k]]) return; int tmp=n-1-use; if(match[s1[tmp]]==-1) { for(int k=n-1;k>=0;k--) { if(!vis[k]) { vis[k]=1;match[s1[tmp]]=k; dfs(use,flag); vis[k]=0;match[s1[tmp]]=-1; } } } else if(match[s2[tmp]]==-1) { for(int k=n-1;k>=0;k--) { if(!vis[k]) { vis[k]=1;match[s2[tmp]]=k; dfs(use,flag); vis[k]=0;match[s2[tmp]]=-1; } } } else if(match[s3[tmp]]==-1) { int pre=match[s1[tmp]]+match[s2[tmp]]+flag; for(int k=0;k<n;k++) if(match[k]==pre%n) return; match[s3[tmp]]=pre%n; vis[match[s3[tmp]]]=1; dfs(use+1,pre>=n); vis[match[s3[tmp]]]=0; match[s3[tmp]]=-1; } else { int pre=match[s1[tmp]]+match[s2[tmp]]+flag; if(match[s3[tmp]]==pre%n) dfs(use+1,pre>=n); } } int main() { scanf("%d%s%s%s",&n,s1,s2,s3); for(int i=0;i<n;i++) { match[i]=-1; s1[i]-=‘A‘;s2[i]-=‘A‘;s3[i]-=‘A‘; }dfs(0); return 0; }
原文：http://www.cnblogs.com/L-Memory/p/7678472.html
