记录编号	452617	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	CSU_Turkey	是否通过	通过
代码语言	C++	运行时间	0.383 s
提交时间	2017-09-19 21:32:21	内存使用	0.31 MiB

#include<bits/stdc++.h>
using namespace std;
int n,s[30],book,h[30];
char a[90],b[30],c[30];
void dfs(int x,int y,int z){
	if(book)return ;
	for(int i=1;i<=x;i++){
		if(s[a[i]-'A']==-1||s[a[i+n]-'A']==-1||s[a[i+2*n]-'A']==-1)continue;
		if((s[a[i]-'A']+s[a[i+n]-'A']+1)%n!=s[a[i+2*n]-'A']&&(s[a[i]-'A']+s[a[i+n]-'A'])%n!=s[a[i+2*n]-'A'])return ;
	}//每次都对所有位进行判断，因为加法最多对下一位加一，所以可以特判一下，如果有一位3个数都被附上值了，而上面两个相加不等于第三个，加一之后也不等于第三个，那么这种情况肯定不合法 
	if(!x){
		if(!y){
			for(int i=0;i<n;i++)cout<<s[i]<<" ";
				book=1;
		}
		return ;
	}
	if(z!=3){
		if(s[a[(z-1)*n+x]-'A']==-1){
			for(int i=0;i<n;i++){
				if(h[i])continue;
				h[i]=1;s[a[(z-1)*n+x]-'A']=i;
				dfs(x,y,z+1);
				h[i]=0;s[a[(z-1)*n+x]-'A']=-1;
			}
		}
		else dfs(x,y,z+1);
	}
	if(z==3){
		if(s[a[2*n+x]-'A']==-1){
			int tem1=s[a[x]-'A']+s[a[x+n]-'A']+y;
			if(!h[tem1%n]){
				s[a[2*n+x]-'A']=tem1%n;h[tem1%n]=1;
				dfs(x-1,tem1/n,1);
				s[a[2*n+x]-'A']=-1;h[tem1%n]=0;
			}
		}
		else if((s[a[x]-'A']+s[a[x+n]-'A']+y)%n==s[a[x+2*n]-'A'])dfs(x-1,(s[a[x]-'A']+s[a[x+n]-'A']+y)/n,1);
	}
}
int main()
{
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
//	freopen("1.txt","r",stdin);
	scanf("%d",&n);
	scanf("%s%s%s",a+1,b+1,c+1);
	for(int i=n+1;i<=2*n;i++)a[i]=b[i-n];
	for(int i=n*2+1;i<=3*n;i++)a[i]=c[i-2*n];
	memset(s,-1,sizeof(s));
	dfs(n,0,1);
	return 0;
}