C++ 70pts 求调 有注释 玄关
查看原帖
C++ 70pts 求调 有注释 玄关
1048193
PengDave楼主2024/1/27 13:48
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
string a,b,c;
long long n;
long long ans[30];
long long o[30],p[30],q[30];
bool vis[30];
bool flag=0;//找没找到答案
long long tmp1=0,tmp2=0;//前两的和,后一个的和
void dfs(long long x){
	if(flag) return;
	if(x==n){
  //判断
		if(tmp1==tmp2){
			for(int i=0;i<n;i++){
				cout<<ans[i]<<" ";
			}
			cout<<endl;
			flag=1;
		}
		return;
	}
   //剪枝
	if(o[0]!=-1&&p[0]!=-1&&q[0]!=-1){
		if((o[0]+p[0])%n!=q[0]){
			return;
		}
	}
	for(long long i=1;i<n;i++){
		if(o[i]!=-1&&p[i]!=-1&&q[i]!=-1){
			if((o[i]+p[i])%n!=q[i]&&(o[i]+p[i]+1)%n!=q[i]){
				return;
			}
			if(i==n-1){
				if(o[i]+p[i]>=n){
					return;
				}
			}
		}
	}
  //枚举每个字母是什么
	for(long long i=0;i<n;i++){
		if(!vis[i]){
			vis[i]=1;
			ans[x]=i;
			long long cnt1=0;//tmp1增加的
			long long cnt2=0;//tmp2增加的
			for(long long j=0;j<n;j++){
				if(a[j]==(x+'A')){
					o[j]=i;
					cnt1+=(long long)(pow(n,j))*i;
				}
				if(b[j]==(x+'A')){
					p[j]=i;
					cnt1+=(long long)(pow(n,j))*i;
				}
				if(c[j]==(x+'A')){
					q[j]=i;
					cnt2+=(long long)(pow(n,j))*i;
				}
			}
			tmp1+=cnt1;
			tmp2+=cnt2;  
			dfs(x+1);
  //回溯
			for(long long j=0;j<n;j++){
				if(a[j]==(x+'A')){
					o[j]=-1;
				}
				if(b[j]==(x+'A')){
					p[j]=-1;
				}
				if(c[j]==(x+'A')){
					q[j]=-1;
				}
			}
			tmp1-=cnt1;
			tmp2-=cnt2;
			vis[i]=0;
			ans[x]=-1;
		}
	}
	return;
}
int main(){
	cin>>n;
	cin>>a>>b>>c;
  //初始化
	memset(ans,-1,sizeof(ans));
	memset(o,-1,sizeof(o));
	memset(p,-1,sizeof(p));
	memset(q,-1,sizeof(q));
	reverse(a.begin(),a.end());
	reverse(b.begin(),b.end());
	reverse(c.begin(),c.end());
  //搜索
	dfs(0);
	return 0;
}
2024/1/27 13:48
加载中...