题意：给出三个由大写字母组成的字符串，每个字母分别表示1-n中的一个数字，并要求满足s1+s2=s3（考虑进位） 分析： 暴力肯定是最直观的方法，复杂度N!，肯定是过不了的。（但就是有人加了剪枝就过了） 正解是高斯消元+暴力枚举 因为有进位问题，所以很容易想到暴力枚举进位，再通过高斯消元来验证。分析一下时间复杂度，暴力2^n-1（第一位不可能进位）*高斯n^3，绝对炸。 换个思路来看，我们可以将进位也看做变量，用高斯消元得出一部分解（方程数小于变量数，不可能解完），再枚举剩下的变量，同时check答案是否合法，因为数据保证有唯一解，所以一定可以枚举出一个合法的方案。高斯消元只需要做一次，复杂就变成2^n-1（枚举仍然是进位） + n^3，可以接受
#include<cstdio> #include<cstring> #include<algorithm> #include<climits> #include<cstdlib> #include<queue> #include<cmath> #define SF scanf #define PF printf #define MAXN 30 using namespace std; int n,m,a[MAXN][MAXN],g[MAXN][MAXN],ans[MAXN],d[MAXN]; char s[3][MAXN]; bool vis[MAXN]; const int add[4]={1,1,-1}; void init(){ SF("%d",&n); SF("%s%s%s",s[0],s[1],s[2]); for(int i=0;i<n;i++) for(int j=0;j<3;j++) a[n-i][s[j][i]-'A'+1]+=add[j]; for(int i=1;i<=n;i++){ g[i][i]=n; g[i][i-1]=-1; } g[1][0]=0; m=n; } int gcd(int x,int y){ if(y==0) return x; return gcd(y,x%y); } void gauss(){ int r,c,maxr,lcm; for(r=1,c=1;r<=n&&c<=m;r++,c++){ maxr=r; for(int i=r+1;i<=n;i++) if(fabs(a[i][c])>fabs(a[maxr][c])) maxr=i; if(!a[maxr][c]){ r--; continue; } if(maxr!=r) for(int i=1;i<=m;i++){ swap(a[r][i],a[maxr][i]); swap(g[r][i],g[maxr][i]); } for(int i=1;i<=n;i++) if(i!=r&&a[i][c]){ lcm=a[i][c]*a[r][c]/gcd(a[i][c],a[r][c]); int t1=lcm/a[i][c]; int t2=lcm/a[r][c]; for(int j=1;j<=m;j++){ g[i][j]=t1*g[i][j]-t2*g[r][j]; a[i][j]=t1*a[i][j]-t2*a[r][j]; } } } } bool check(){ memset(vis,0,sizeof vis); for(int i=1;i<=n;i++){ ans[i]=0; for(int j=1;j<=n;j++) ans[i]+=g[i][j]*d[j]; if(ans[i]%a[i][i]||ans[i]/a[i][i]<0||ans[i]/a[i][i]>=n||vis[ans[i]/a[i][i]]) return 0; ans[i]/=a[i][i]; vis[ans[i]]=1; } return 1; } void print_ans(){ for(int i=1;i<=n;i++){ PF("%d",ans[i]); if(i==n) PF("\n"); else PF(" "); } } void dfs(int x){ if(x==n){ if(check()){ print_ans(); exit(0); } return ; } d[x]=1; dfs(x+1); d[x]=0; dfs(x+1); } int main(){ init(); gauss(); dfs(1); }