80分求调!
查看原帖
80分求调!
980719
zhangjunxizjx楼主2025/8/3 13:55

#88 #99 TLETLE

求调!!!感谢!!!

#include <bits/stdc++.h>
using namespace std;
int n;
string a,b,c;
int la[222],lb[222],lc[222];// 把三个字符串转化为数字存储

int lis[222];// 存储每个字母代表的值 



bool used[222];// 存储用过的值 



bool order_ban[222];//用于生成测试顺序 
int order[222];
int order_count = 0;


bool check(){// 剪枝 
	for(int dig = n;dig >= 1;dig--){
		if(lis[la[dig]] != -1 and lis[lb[dig]] != -1 and lis[lc[dig]] != -1){
			int head = lis[la[dig]]+lis[lb[dig]];
			int tail = lis[lc[dig]];
			if (!(head % n == tail or (head+1) % n == tail)){
				return false;
			}
		}
	}
	return true;
}
bool last_check(){ // 最终的检验 
	int carry = 0;//存储进位 
	for(int test = n;test >= 1;test--){
		if((lis[la[test]] + lis[lb[test]] + carry) % n != lis[lc[test]]){
			return false;
		}
		else{
			if((lis[la[test]] + lis[lb[test]] + carry) >= n){
				carry = 1;
				if(test == 1){
					return false;
				}
			} 
			else{
				carry = 0;
			}
		}
	}
	return true;
}
void dfs(int dig){//开搜 
	if(dig == 0){
		if(last_check()){
			for(int i = 1;i <= n;i++){
				cout << lis[i] << ' '; 
			}
			return; 
		}
		else{
			return; 
		}
	}
	else{
		for(int i = 0;i < n;i++){
			if(used[i]){
				continue;
			}
			else{
				lis[order[n-dig+1]] = i;
				used[i] = 1;
				if(check()){
					dfs(dig-1);
				}
				lis[order[n-dig+1]] = -1;
				used[i] = 0;
			}
		}
	} 
}
int main(){
	cin >> n;
	cin >> a >> b >> c;
	a = ' '+a;
	b = ' '+b;
	c = ' '+c;
	for(int i = 1;i <= n;i++){
		la[i]=a[i] -'A'+1;
		lb[i]=b[i] -'A'+1;
		lc[i]=c[i] -'A'+1;
	}
	for(int i = n;i >= 1;i--){//生成遍历顺序,便于剪枝 
		if(order_ban[la[i]] == 0){
			order_ban[la[i]] = 1;
			order_count += 1;
			order[order_count] = la[i];
		}
		if(order_ban[lb[i]] == 0){
			order_ban[lb[i]] = 1;
			order_count += 1;
			order[order_count] = lb[i];
		}
		if(order_ban[lc[i]] == 0){
			order_ban[lc[i]] = 1;
			order_count += 1;
			order[order_count] = lc[i];
		}
	}
	for(int i = 1;i <= n;i++){
		lis[i] = - 1;
	}
	dfs(n);
}
2025/8/3 13:55
加载中...