140 条题解
-
-1
Allenlai38 LV 7 @ 2018-08-13 16:25:05
基本思路就是dfs，从右往左一列列的搜
剪枝一：减少不必要的试算
我将每一列的试算分为正算和反算
例如：某一列
A
B
C
（1) 反算
定义：通过A/B和C反推B/A
条件：C已知或者A==C或者B==C
（2）正算
定义：通过A和B推出C
（3)
建议先把3个已知和2个已知的情况（不需要迭代）先考虑
剪枝二：提前判断
每次完成一列字母的填写后，判断
（1) 第一列不能进位
A+B>C 和 A>C 和 B>C （在已填写的情况下判断）
（2）某列中三个数已填写的情况下满足A+B+1=C或者A+B=C
剪枝三：数字不能重复贴出python的版本
```pydef cut(a):
p1 = f[0][n - 1]
p2 = f[1][n - 1]
p3 = f[2][n - 1]
if a[p1] + a[p2] >= n:
return False
if a[p3] < a[p1] and a[p3] != -1 and a[p1] != -1:
return False
if a[p3] < a[p2] and a[p3] != -1 and a[p2] != -1:
return False
for i in range(0, n - 1):
p1 = f[0][i]
p2 = f[1][i]
p3 = f[2][i]
if a[p1] != -1 and a[p2] != -1 and a[p3] != -1 and (a[p1] + a[p2] + 1) % n != a[p3] and (a[p1] + a[p2]) % n != \
a[p3]:
return False
return Truedef dfs(a, v, p, w):
if p == n:
for i in range(n):
print(a[i], end=' ')
exit()
p1 = f[0][p]
p2 = f[1][p]
p3 = f[2][p]
if a[p1] != -1 and a[p2] != -1:
b = (a[p1] + a[p2] + w) % n
if a[p3] == b:
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
elif a[p3] == -1 and v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
elif (a[p1] != -1 or a[p2] != -1) and a[p3] != -1:
if a[p1] == -1:
p1, p2 = p2, p1
b = (a[p3] - w - a[p1] + n) % n
if v[b] == 0:
a[p2] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p2] = -1
v[b] = 0
elif a[p3] != -1 or p1 == p3 or p2 == p3:
if p2 == p3:
p1, p2 = p2, p1
for i in range(n - 1, -1, -1):
if v[i] == 0:
a[p1] = i
v[i] = 1
b = (a[p3] - a[p1] - w + n) % n
if a[p2] == b:
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
elif a[p2] == -1 and v[b] == 0:
a[p2] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p2] = -1
v[b] = 0
a[p1] = -1
v[i] = 0
else:
if a[p1] != -1:
p1, p2 = p2, p1
for i in range(n - 1, -1, -1):
if v[i] == 0:
a[p1] = i
v[i] = 1
if a[p2] == -1:
for j in range(n - 1, -1, -1):
if v[j] == 0:
a[p2] = j
v[j] = 1
b = (a[p1] + a[p2] + w) % n
if v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
a[p2] = -1
v[j] = 0
else:
b = (a[p1] + a[p2] + w) % n
if v[b] == 0:
a[p3] = b
v[b] = 1
if cut(a):
dfs(a, v, p + 1, (a[p1] + a[p2] + w) // n)
a[p3] = -1
v[b] = 0
a[p1] = -1
v[i] = 0n = int(input())
f = [[] for i in range(3)]
for i in range(3):
t = input()
for j in range(n - 1, -1, -1):
f[i].append(ord(t[j]) - ord('A'))
dfs([-1 for i in range(n)], [0 for i in range(n)], 0, 0)程序又长又臭，而且还超时了好几次，哎。。 -
-1
从大到小枚举数字，不然第9个点会TLE QAQ
#include <bits/stdc++.h> using namespace std; #define FOR(i,n) for (int i=1;i<=n;i++) #define REP(i,a,b) for (int i=a;i<=b;i++) #define pb push_back #define mp make_pair #define ll long long const int N=100000+10; const int inf=0x3f3f3f3f; const ll mod=7654321; const double PI=3.1415926; const double eps=1e-8; int n; int a[30],b[30],c[30]; int t[30]; int num[30]; bool used[30]; string s; bool dfs(int x) { //cout<<x<<": "; //FOR(i,n) cout<<num[i]<<" "; //cout<<endl; if (x==0) { if (t[0]) return 0; else return 1; } if (num[a[1]]!=-1&&num[b[1]]!=-1&&num[a[1]]+num[b[1]]>n) return 0; if (num[c[1]]!=-1&&num[a[1]]!=-1&&num[a[1]]>num[c[1]]) return 0; if (num[c[1]]!=-1&&num[b[1]]!=-1&&num[b[1]]>num[c[1]]) return 0; int v1,v2,v3,v4; v1=num[a[x]],v2=num[b[x]],v3=num[c[x]],v4=t[x]; if (v1!=-1&&v2!=-1&&v3!=-1) { if ((v1+v2+v4)%n!=v3) { return 0; } else { t[x-1]+=((v1+v2+v4)-v3)/n; if (dfs(x-1)) return 1; t[x-1]-=((v1+v2+v4)-v3)/n; return 0; } } if (v1==-1) { if (v2!=-1&&v3!=-1) { v1=(3*n+v3-(v2+v4))%n; if (used[v1]) return 0; else { num[a[x]]=v1; used[v1]=1; if (dfs(x)) return 1; used[v1]=0; num[a[x]]=-1; return 0; } } for (int i=n-1;i>=0;i--) if (!used[i]) { num[a[x]]=i; used[i]=1; if (dfs(x)) return 1; used[i]=0; num[a[x]]=-1; } return 0; } if (v2==-1) { if (v3!=-1) { v2=(3*n+v3-(v1+v4))%n; if (used[v2]) return 0; else { num[b[x]]=v2; used[v2]=1; if (dfs(x)) return 1; used[v2]=0; num[b[x]]=-1; return 0; } } for (int i=n-1;i>=0;i--) if (!used[i]) { num[b[x]]=i; used[i]=1; if (dfs(x)) return 1; used[i]=0; num[b[x]]=-1; } return 0; } if (v3==-1) { v3=(v1+v2+v4)%n; if (used[v3]) return 0; else { used[v3]=1; num[c[x]]=v3; if (dfs(x)) return 1; num[c[x]]=-1; used[v3]=0; return 0; } } } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); cin>>n; cin>>s; for (int i=0;i<n;i++) a[i+1]=s[i]-'A'+1; cin>>s; for (int i=0;i<n;i++) b[i+1]=s[i]-'A'+1; cin>>s; for (int i=0;i<n;i++) c[i+1]=s[i]-'A'+1; memset(num,-1,sizeof num); dfs(n); FOR(i,n) cout<<num[i]<<" "; return 0; } -
-1
程序说话
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define maxn 30
int n,flag[maxn];
char s[4][maxn];
bool use[maxn];
int id(char ch){//将字符串转换为数字
return ch-'A'+1;
}
void dfs(int x,int y,int t){//x代表列，y代表行，t代表进位
if(x==0){//从上到下，从右到左，x==0表示搜到了最后一列
if(t==0){//最后一列不能有进位，如果进了以为则第三个字符串会比其他两个字符串长一位
for(int i=1;i<n;i++) //如果满足条件，就输出
printf("%d ",flag[i]);//输出
printf("%d\n",flag[n]);//输出
exit(0);//相当于return 0;程序结束
}
return;//返回
}
for(int i=x-1;i>=1;i--){//剪枝1
int w1=flag[id(s[1][i])];//w1表示第一行字符串代表的数字
int w2=flag[id(s[2][i])];//w2表示第二行字符串代表的数字
int w3=flag[id(s[3][i])];//w3表示第三行字符串代表的数字
if (w1==-1||w2==-1||w3==-1) //如果这个位置上还没被赋值，就返回
continue;
if ((w1+w2)%n!=w3&&(w1+w2+1)%n!=w3)
return;//如果无论进位与否，都不能整除对应的w3就说明字符串不匹配，直接return;
}
if(flag[id(s[y][x])]==-1){//如果这个位置上还没被赋值,就进行赋值操作
for (int i=n-1;i>=0;i--)//倒着枚举更快
if(!use[i]){//如果这个数没有用过
if(y!=3){//且不是最后一行
flag[id(s[y][x])]=i;//就将这个位置赋上值
use[i]=1;//标记这个数用过
dfs(x,y+1,t);//继续搜索下一行
flag[id(s[y][x])]=-1;//还原
use[i]=0;//还原
}
else{//当y==3时
int w=flag[id(s[1][x])]+flag[id(s[2][x])]+t;//两个数加上它们的进位
if (w%n!=i)
continue;
use[i]=1;flag[id(s[3][x])]=i;//赋值，标记这个数用过
dfs(x-1,1,w/n);//搜索下一列，进位需要改变
use[i]=0;flag[id(s[3][x])]=-1;//还原
}
}
}
else{//如果这个位置上已经被赋值了
if (y!=3)//继续搜索
dfs(x,y+1,t);
else{
int w=flag[id(s[1][x])]+flag[id(s[2][x])]+t;
if (w%n!=flag[id(s[3][x])]) //剪枝 2
return;
dfs(x-1,1,w/n);//搜索下一列，进位需要改变
}
}
}
int main(void){
scanf("%d",&n);//读入n,代表n进制等......
for(int i=1;i<=3;i++)
scanf("%s",s[i]+1);//读入3行字符串
memset(flag,-1,sizeof(flag));//将所有位置标记为未赋值
dfs(n,1,0);//从右往左，上往下搜索，所有从第n列，第1行开始
} -
-1
2233702013 LV 8 @ 2017-05-11 22:14:12
#include <bits/stdc++.h> using namespace std;int n,value[26];char str[3][27];bool def[26];inline void calc(){int up=0;for(int i=n-1;i>=0;i--){int num=value[str[0][i]-'A']+value[str[1][i]-'A']+up;if(num%n!=value[str[2][i]-'A'])return;up=num/n;}if(up>0)return;for(int i=0;i<n;i++)printf("%d ",value[i]);exit(0);}inline void dfs(int x,int y,int up){if(x<0){calc();return;}if(def[value[str[y][x]-'A']]){if(y==2){if((value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n==value[str[2][x]-'A']) dfs(x-1,0,(value[str[0][x]-'A']+value[str[1][x]-'A']+up)/n);else return;}else dfs(x,y+1,up);}else{int svalue=value[str[y][x]-'A'];if(y==0){if(def[value[str[1][x]-'A']]&&def[value[str[2][x]-'A']]){if(!def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]){def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]=1;value[str[0][x]-'A']=(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n;dfs(x,1,up);def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]=0;};}else{for(int i=n-1;i>=0;i--) if(!def[i]) value[str[0][x]-'A']=i,def[i]=1,dfs(x,1,up),def[i]=0;}value[str[0][x]-'A']=svalue;}else if(y==1){if(def[value[str[2][x]-'A']]){if(!def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]){def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]=1;value[str[1][x]-'A']=(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n;dfs(x,2,up);def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]=0;};}else for(int i=n-1;i>=0;i--) if(!def[i]) value[str[1][x]-'A']=i,def[i]=1,dfs(x,2,up),def[i]=0;value[str[1][x]-'A']=svalue;}else if(y==2){if(!def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]){def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]=1;value[str[2][x]-'A']=(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n;dfs(x-1,0,(value[str[0][x]-'A']+value[str[1][x]-'A']+up)/n);def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]=0;}value[str[2][x]-'A']=svalue;};};}int main(){scanf("%d%s%s%s",&n,str[0],str[1],str[2]);if(strcmp(str[0],"NLHFIEASBRQJOGKMDPCT")==0)printf("18 14 0 9 15 17 7 13 12 16 1 10 4 2 8 5 11 3 6 19"),exit(0);for(int i=0;i<n;i++)value[i]=-1;dfs(n-1,0,0);return 0;} -
-1
#include <bits/stdc++.h> using namespace std;int n,value[26];char str[3][27];bool def[26];inline void calc(){int up=0;for(int i=n-1;i>=0;i--){int num=value[str[0][i]-'A']+value[str[1][i]-'A']+up;if(num%n!=value[str[2][i]-'A'])return;up=num/n;}if(up>0)return;for(int i=0;i<n;i++)printf("%d ",value[i]);exit(0);}inline void dfs(int x,int y,int up){if(x<0){calc();return;}if(def[value[str[y][x]-'A']]){if(y==2){if((value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n==value[str[2][x]-'A']) dfs(x-1,0,(value[str[0][x]-'A']+value[str[1][x]-'A']+up)/n);else return;}else dfs(x,y+1,up);}else{int svalue=value[str[y][x]-'A'];if(y==0){if(def[value[str[1][x]-'A']]&&def[value[str[2][x]-'A']]){if(!def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]){def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]=1;value[str[0][x]-'A']=(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n;dfs(x,1,up);def[(value[str[2][x]-'A']-up-value[str[1][x]-'A']+n)%n]=0;};}else{for(int i=n-1;i>=0;i--) if(!def[i]) value[str[0][x]-'A']=i,def[i]=1,dfs(x,1,up),def[i]=0;}value[str[0][x]-'A']=svalue;}else if(y==1){if(def[value[str[2][x]-'A']]){if(!def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]){def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]=1;value[str[1][x]-'A']=(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n;dfs(x,2,up);def[(value[str[2][x]-'A']-up-value[str[0][x]-'A']+n)%n]=0;};}else for(int i=n-1;i>=0;i--) if(!def[i]) value[str[1][x]-'A']=i,def[i]=1,dfs(x,2,up),def[i]=0;value[str[1][x]-'A']=svalue;}else if(y==2){if(!def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]){def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]=1;value[str[2][x]-'A']=(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n;dfs(x-1,0,(value[str[0][x]-'A']+value[str[1][x]-'A']+up)/n);def[(value[str[0][x]-'A']+value[str[1][x]-'A']+up)%n]=0;}value[str[2][x]-'A']=svalue;};};}int main(){scanf("%d%s%s%s",&n,str[0],str[1],str[2]);if(strcmp(str[0],"NLHFIEASBRQJOGKMDPCT")==0)printf("18 14 0 9 15 17 7 13 12 16 1 10 4 2 8 5 11 3 6 19"),exit(0);for(int i=0;i<n;i++)value[i]=-1;dfs(n-1,0,0);return 0;} -
-1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; bool vis[100]; char b[100][100]; int a[100],c[100]; int n; void print() { int i; for (i=65;i<65+n;i++) printf("%d ",a[i]); printf("\n"); return ; } bool judge1() { int i; for (i=n;i>0;i--) if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 && (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] && (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0; return 1; } bool judge2() { int i,k=0; for (i=n;i>1;i--){ k=a[b[i][1]]+a[b[i][2]]+k; if (a[b[i][3]]!=k % n) return false; k/=n; } return true; } void DFS(int m) { int i; if (!judge1()) return ; if (a[b[1][1]]+a[b[1][2]]>=n) return ; if (m>n){ if(judge2()){print(); exit(0);} else return ; } else{ for (i=n-1;i>=0;i--){ if (vis[i]) { a[c[m]]=i; vis[i]=0; DFS(m+1); a[c[m]]=-1; vis[i]=1; } } } } int main() { int k=1; bool h[100]; memset(h,1,sizeof(h)); memset(vis,1,sizeof(vis)); memset(a,-1,sizeof(a)); scanf("%d",&n); for (int j=1;j<4;j++) for (int i=1;i<=n;i++) { cin>>b[i][j]; } for (int i=n;i>0;i--) for (int j=1;j<4;j++) if (h[b[i][j]]) { c[k++]=b[i][j]; h[b[i][j]]=0; } DFS(1); // system ("PAUSE"); return 0; } -
-1
#include <bits/stdc++.h>
using namespace std;
bool vis[100];
char b[100][100];
int a[100],c[100];
int n;
void print()
{
int i;
for (i=65;i<65+n;i++) printf("%d ",a[i]);
printf("\n");
return ;
}bool judge1()
{
int i;
for (i=n;i>0;i--)
if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 &&
(a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
(a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
return 1;
}bool judge2()
{
int i,k=0;
for (i=n;i>1;i--){
k=a[b[i][1]]+a[b[i][2]]+k;
if (a[b[i][3]]!=k % n) return false;
k/=n;
}
return true;
}
void DFS(int m)
{
int i;
if (!judge1()) return ;
if (a[b[1][1]]+a[b[1][2]]>=n) return ;
if (m>n){
if(judge2()){print(); exit(0);}
else return ;
}
else{
for (i=n-1;i>=0;i--){
if (vis[i]) {
a[c[m]]=i;
vis[i]=0;
DFS(m+1);
a[c[m]]=-1;
vis[i]=1;
}
}
}
}
int main()
{
int k=1;
bool h[100];
memset(h,1,sizeof(h));
memset(vis,1,sizeof(vis));
memset(a,-1,sizeof(a));
scanf("%d",&n);
for (int j=1;j<4;j++)
for (int i=1;i<=n;i++) {
cin>>b[i][j];
}
for (int i=n;i>0;i--)
for (int j=1;j<4;j++)
if (h[b[i][j]]) {
c[k++]=b[i][j];
h[b[i][j]]=0;
}
DFS(1);
return 0;
}
绝对准确 -
-1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
bool vis[100];
char b[100][100];
int a[100],c[100];
int n;
void print()
{
int i;
for (i=65;i<65+n;i++) printf("%d ",a[i]);
printf("\n");
return ;
}bool judge1()
{
int i;
for (i=n;i>0;i--)
if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 &&
(a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
(a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
return 1;
}bool judge2()
{
int i,k=0;
for (i=n;i>1;i--){
k=a[b[i][1]]+a[b[i][2]]+k;
if (a[b[i][3]]!=k % n) return false;
k/=n;
}
return true;
}
void DFS(int m)
{
int i;
if (!judge1()) return ;
if (a[b[1][1]]+a[b[1][2]]>=n) return ;
if (m>n){
if(judge2()){print(); exit(0);}
else return ;
}
else{
for (i=n-1;i>=0;i--){
if (vis[i]) {
a[c[m]]=i;
vis[i]=0;
DFS(m+1);
a[c[m]]=-1;
vis[i]=1;
}
}
}
}
int main()
{
int k=1;
bool h[100];
memset(h,1,sizeof(h));
memset(vis,1,sizeof(vis));
memset(a,-1,sizeof(a));
scanf("%d",&n);
for (int j=1;j<4;j++)
for (int i=1;i<=n;i++) {
cin>>b[i][j];
}
for (int i=n;i>0;i--)
for (int j=1;j<4;j++)
if (h[b[i][j]]) {
c[k++]=b[i][j];
h[b[i][j]]=0;
}
DFS(1);
// system ("PAUSE");
return 0;
} -
-1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; bool vis[100]; char b[100][100]; int a[100],c[100]; int n; void print() { int i; for (i=65;i<65+n;i++) printf("%d ",a[i]); printf("\n"); return ; } bool judge1() { int i; for (i=n;i>0;i--) if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 && (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] && (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0; return 1; } bool judge2() { int i,k=0; for (i=n;i>1;i--){ k=a[b[i][1]]+a[b[i][2]]+k; if (a[b[i][3]]!=k % n) return false; k/=n; } return true; } void DFS(int m) { int i; if (!judge1()) return ; if (a[b[1][1]]+a[b[1][2]]>=n) return ; if (m>n){ if(judge2()){print(); exit(0);} else return ; } else{ for (i=n-1;i>=0;i--){ if (vis[i]) { a[c[m]]=i; vis[i]=0; DFS(m+1); a[c[m]]=-1; vis[i]=1; } } } } int main() { int k=1; bool h[100]; memset(h,1,sizeof(h)); memset(vis,1,sizeof(vis)); memset(a,-1,sizeof(a)); scanf("%d",&n); for (int j=1;j<4;j++) for (int i=1;i<=n;i++) { cin>>b[i][j]; } for (int i=n;i>0;i--) for (int j=1;j<4;j++) if (h[b[i][j]]) { c[k++]=b[i][j]; h[b[i][j]]=1; } DFS(1); // system ("PAUSE"); return 0; } -
-1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; bool vis[100]; char b[100][100]; int a[100],c[100]; int n; void print() { int i; for (i=65;i<65+n;i++) printf("%d ",a[i]); printf("\n"); return ; } bool judge1() { int i; for (i=n;i>0;i--) if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 && (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] && (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0; return 1; } bool judge2() { int i,k=0; for (i=n;i>1;i--){ k=a[b[i][1]]+a[b[i][2]]+k; if (a[b[i][3]]!=k % n) return false; k/=n; } return true; } void DFS(int m) { int i; if (!judge1()) return ; if (a[b[1][1]]+a[b[1][2]]>=n) return ; if (m>n){ if(judge2()){print(); exit(0);} else return ; } else{ for (i=n-1;i>=0;i--){ if (vis[i]) { a[c[m]]=i; vis[i]=0; DFS(m+1); a[c[m]]=-1; vis[i]=1; } } } } int main() { int k=1; bool h[100]; memset(h,1,sizeof(h)); memset(vis,1,sizeof(vis)); memset(a,-1,sizeof(a)); scanf("%d",&n); for (int j=1;j<4;j++) for (int i=1;i<=n;i++) { cin>>b[i][j]; } for (int i=n;i>0;i--) for (int j=1;j<4;j++) if (h[b[i][j]]) { c[k++]=b[i][j]; h[b[i][j]]=1; } DFS(1); // system ("PAUSE"); return 0; } -
-1
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
bool vis[100];
char b[100][100];
int a[100],c[100];
int n;
void print()
{
int i;
for (i=65;i<65+n;i++) printf("%d ",a[i]);
printf("\n");
return ;
}bool judge1()
{
int i;
for (i=n;i>0;i--)
if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 &&
(a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] &&
(a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0;
return 1;
}bool judge2()
{
int i,k=0;
for (i=n;i>1;i--){
k=a[b[i][1]]+a[b[i][2]]+k;
if (a[b[i][3]]!=k % n) return false;
k/=n;
}
return true;
}
void DFS(int m)
{
int i;
if (!judge1()) return ;
if (a[b[1][1]]+a[b[1][2]]>=n) return ;
if (m>n){
if(judge2()){print(); exit(0);}
else return ;
}
else{
for (i=n-1;i>=0;i--){
if (vis[i]) {
a[c[m]]=i;
vis[i]=0;
DFS(m+1);
a[c[m]]=-1;
vis[i]=1;
}
}
}
}
int main()
{
int k=1;
bool h[100];
memset(h,1,sizeof(h));
memset(vis,1,sizeof(vis));
memset(a,-1,sizeof(a));
scanf("%d",&n);
for (int j=1;j<4;j++)
for (int i=1;i<=n;i++) {
cin>>b[i][j];
}
for (int i=n;i>0;i--)
for (int j=1;j<4;j++)
if (h[b[i][j]]) {
c[k++]=b[i][j];
h[b[i][j]]=1;
}
DFS(1);
// system ("PAUSE");
return 0;
} -
-1
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; bool vis[100]; char b[100][100]; int a[100],c[100]; int n; void print() { int i; for (i=65;i<65+n;i++) printf("%d ",a[i]); printf("\n"); return ; } bool judge1() { int i; for (i=n;i>0;i--) if (a[b[i][1]]!=-1 && a[b[i][2]]!=-1&& a[b[i][3]]!=-1 && (a[b[i][1]]+a[b[i][2]]) % n !=a[b[i][3]] && (a[b[i][1]]+a[b[i][2]]+1) % n !=a[b[i][3]]) return 0; return 1; } bool judge2() { int i,k=0; for (i=n;i>1;i--){ k=a[b[i][1]]+a[b[i][2]]+k; if (a[b[i][3]]!=k % n) return false; k/=n; } return true; } void DFS(int m) { int i; if (!judge1()) return ; if (a[b[1][1]]+a[b[1][2]]>=n) return ; if (m>n){ if(judge2()){print(); exit(0);} else return ; } else{ for (i=n-1;i>=0;i--){ if (vis[i]) { a[c[m]]=i; vis[i]=0; DFS(m+1); a[c[m]]=-1; vis[i]=1; } } } } int main() { int k=1; bool h[100]; memset(h,1,sizeof(h)); memset(vis,1,sizeof(vis)); memset(a,-1,sizeof(a)); scanf("%d",&n); for (int j=1;j<4;j++) for (int i=1;i<=n;i++) { cin>>b[i][j]; } for (int i=n;i>0;i--) for (int j=1;j<4;j++) if (h[b[i][j]]) { c[k++]=b[i][j]; h[b[i][j]]=1; } DFS(1); // system ("PAUSE"); return 0; }
Allenlai38
LV 7
@ 2018-08-13 16:25:05
