闲谈:
1.这个题就是给你一个N进制数和N位,给出A和B的固定格式,以及C且C的格式,且A+B=C且不能进位.要你求A、B、C中每个字符所代表的每个数字.
2.这题我们由于最后不能进位可知最后一位进位必定return.
3.然后从第一位开始判断是否合法即可.
代码:
#include <bits/stdc++.h> using namespace std; const int N=30; int n; char an[3][N]; bool st[N]; int path[N]; int q[N]; bool ck() { for (int i=n-1,t=0;i>=0;i--) { int a=an[0][i]-'A',b=an[1][i]-'A',c=an[2][i]-'A'; if(path[a]!=-1&&path[b]!=-1&&path[c]!=-1) { a=path[a],b=path[b],c=path[c]; if(t!=-1) { if((a+b+t)%n!=c) return false; if(!i&&a+b+t>=n) return false; t=(a+b+t)/n; } else { if ((a+b)%n!=c&&(a+b+1)%n!=c) return false; if (!i&&a+b>=n) return false; } } else t=-1; } return true; } bool dfs(int u)//现在填了几个数了 { if(u==n) return true; for(int i=0;i<n;i++)//枚举填哪个数. { if(!st[i])//假如这个数没有被用过. { path[q[u]]=i; st[i]=true; if(ck()&&dfs(u+1)) return true; path[q[u]]=-1; st[i]=false; } } return false; } int main() { cin>>n; for(int i=0;i<3;i++) scanf("%s",an[i]);//输入 for(int i=n-1,k=0;i>=0;i--) { for(int j=0;j<3;j++) { int t=an[j][i]-'A'; if(!st[t])//假如没出现过. { st[t]=true; q[k++]=t; } } } memset(st,0,sizeof st); memset(path,-1,sizeof path); dfs(0); for(int i=0;i<n;i++) cout<<path[i]<<' '; cout<<endl; return 0; }