1 条题解
-
0
C++ :
/* 枚举全排列,并且加了来了两个剪枝 ①当一列竖式中的字母已全部枚举,且不符合要求; ②当一列竖式中的字母已枚举2个,另一个数字已被使用; (剪枝时注意进位) */ #include<iostream> #include<cstdio> #include<cstring> #define M 27 using namespace std; char s[4][M]; int n,now; int a[M],b[M],c[M]; bool goal; bool Judge() { int temp=0,k=0; for (int i=n-1;i>=0;--i) { temp=(b[s[1][i]-'A']+b[s[2][i]-'A']+k)%n; k=(b[s[1][i]-'A']+b[s[2][i]-'A']+k)/n; if (temp!=b[s[3][i]-'A']) return 0; } return 1; } bool Cleck()//剪枝 { int temp,t1,t2,t3; for(int i=n-1;i>=0;i--) { t1=s[1][i]-'A',t2=s[2][i]-'A',t3=s[3][i]-'A'; if(b[t1]!=-1&&b[t2]!=-1&&b[t3]!=-1) { if((b[t1]+b[t2]+1)%n==b[t3]||(b[t1]+b[t2])%n==b[t3]) continue; else return 0; } if (b[t1]!=-1 && b[t2]!=-1) { temp=(b[t1]+b[t2])%n; if (a[temp]==-1||a[(temp+1)%n]==-1)continue; else return 0; } if (b[t1]!=-1&&b[t3]!=-1) { temp=b[t3]-b[t1]; if(temp>=0&&a[temp]==-1)continue; temp+=n; if(temp>=0&&a[temp]==-1)continue; temp=b[t3]-b[t1]-1; if(temp>=0&&a[temp]==-1)continue; temp+=n; if(temp>=0&&a[temp]==-1)continue; return 0; } if (b[t2]!=-1 && b[t3]!=-1) { temp=b[t3]-b[t2]; if(temp>=0&&a[temp]==-1)continue; temp+=n; if(temp>=0&&a[temp]==-1)continue; temp=b[t3]-b[t2]-1; if(temp>=0&&a[temp]==-1)continue; temp+=n; if(temp>=0&&a[temp]==-1)continue; return 0; } } return 1; } void DFS(int k) { if(k>n) { if (Judge()) goal=1; return; } for(int i=n-1;i>=0;--i) if(a[i]==-1) { a[i]=c[k]; b[c[k]]=i; if(Cleck()) DFS(k+1); if(goal) return; a[i]=-1; b[c[k]]=-1; } } int main() { scanf("%d",&n); scanf("%s",s[1]); scanf("%s",s[2]); scanf("%s",s[3]); memset(a,255,sizeof(a)); for(int i=n-1;i>=0;i--) for(int j=1;j<=3;j++) if (b[s[j][i]-'A']==0) { b[s[j][i]-'A']=-1; c[++now]=s[j][i]-'A'; } DFS(1); for(int i=0;i<n;i++) printf("%d ",b[i]); return 0; }
信息
- ID
- 1089
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 1
- 已通过
- 1
- 上传者