70pts,双剪枝,TLE#7,8,9,求助
查看原帖
70pts,双剪枝,TLE#7,8,9,求助
367897
yuzh2005楼主2023/8/2 16:04
#include<bits/stdc++.h>
using namespace std;
int n,ton;
bool flag=false;
char ori1[27],ori2[27],ori3[27];
int num1[27],num2[27],ans[27];
int dict[27],add[27];
bool used[27];
template<typename T>inline void qread(T &x)
{
x=0;int f=0;char ch=getchar();
while(ch<'0'||ch>'9') {f|=(ch=='-');ch=getchar();}
while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?-x:x;
return;
}
inline int trans(char x){
	return ((int)x-64);
}
inline bool rule_1(){
	if(dict[num1[1]]+dict[num2[1]]>=n) return false;
	else return true;
}
inline bool rule_2(){
	for(int i=n;i>0;i--){
		if(dict[num1[i]]==-1||dict[num2[i]]==-1||dict[ans[i]]==-1) continue;
		else{
			if((dict[num1[i]]+dict[num2[i]])%n!=dict[ans[i]]&&(dict[num1[i]]+dict[num2[i]]+1)%n!=dict[ans[i]]){
				return false;
			}
		}
	}
	return true;
}
inline bool check(){
	for(int i=n;i>=1;i--){
		if((dict[num1[i]]+dict[num2[i]]+add[i]<n)&&(dict[num1[i]]+dict[num2[i]]+add[i]==dict[ans[i]])){
			continue;
		}
		if((dict[num1[i]]+dict[num2[i]]+add[i]>=n)&&(dict[num1[i]]+dict[num2[i]]+add[i]-n==dict[ans[i]])){
			add[i-1]=1;
			continue;
		}
		else{
			memset(add,0,sizeof(add));
			return false;
		}
	}
	memset(add,0,sizeof(add));
	return true;
}
inline void search(int x){
	for(int i=n-1;i>=0;i--){
		if(ton==n){
			if(check()==true) {
				flag=true;
				return;
			}
			else{
				flag=false;
				return;
			}
		}
		if(used[i]==1) continue;
		if(ton!=n&&used[i]==0&&rule_1()==true&&rule_2()==true){
			used[i]=1;
			dict[x]=i;
			ton++;
			if(rule_1()==true&&rule_2()==true) search(x-1);
			else{
				used[i]=0;
				dict[x]=-1;
				--ton;
				continue;
			}
		if(flag==true) return;
		else{
			used[i]=0;
			dict[x]=-1;
			--ton;
			continue;
		}
		
	}
	} 
	return;
}      
int main(){
	qread(n);
	memset(dict,-1,sizeof(dict));  
	memset(add,0,sizeof(add));
	memset(used,false,sizeof(used));
	for(int i=1;i<=n;i++){
		cin>>ori1[i]; num1[i]=trans(ori1[i]);
	}
	for(int i=1;i<=n;i++){
		cin>>ori2[i]; num2[i]=trans(ori2[i]);
	}
	for(int i=1;i<=n;i++){
		cin>>ori3[i]; ans[i]=trans(ori3[i]);
	}
	search(n); 
	for(int i=1;i<=n;i++){
		cout<<dict[i]<<" ";
	}
	return 0;
}
2023/8/2 16:04
加载中...