记录编号	451280	评测结果	WWWWWWWWWW
题目名称	[NOIP 2004]虫食算	最终得分	0
用户昵称	LadyLex	是否通过	未通过
代码语言	C++	运行时间	1.782 s
提交时间	2017-09-17 15:05:33	内存使用	0.26 MiB

#include <cstdio>
#include <cstring>
using namespace std;
const int N=126;
char s[3][N];
int n,key[N],pre[N],nxt[N];
bool vis[N];
inline bool Legal(int pos,int val0,int val1,int val2)
{
	if(s[0][pos]==s[1][pos]&&val0!=val1)return 0;
	if(s[0][pos]==s[2][pos]&&val0!=val2)return 0;
	if(s[1][pos]==s[2][pos]&&val1!=val2)return 0;
	if(s[0][pos]!=s[1][pos]&&val0==val1)return 0;
	if(s[0][pos]!=s[2][pos]&&val0==val2)return 0;
	if(s[1][pos]!=s[2][pos]&&val1==val2)return 0;
	return 1;
}
inline bool dfs(int pos,int up)
{
	if(!pos)
		if(up)return 0;
		else return 1;
	int &k0=key[s[0][pos]],&k1=key[s[1][pos]],&k2=key[s[2][pos]];
	register int i,j;
	if(k0!=-1)
		if(k1!=-1)
			if(k2!=-1)
				if((up+k0+k1)%n!=k2)return 0;
				else return dfs(pos-1,k0+k1+up>=n);
			else
				if(!vis[(up+k0+k1)%n])
				{
					k2=(up+k0+k1)%n,vis[k2]=1;
					if(dfs(pos-1,k0+k1+up>=n))return 1;
					vis[k2]=0,k2=-1;return 0;
				}
				else return 0;
		else
			if(k2!=-1)
				if(!vis[(k2-k0-up+n)%n])
				{
					k1=(k2-k0-up+n)%n;vis[k1]=1;
					if(dfs(pos-1,k0+k1+up>=n))return 1;
					vis[k1]=0,k1=-1;return 0;
				}
				else return 0;
			else
			{
				for(j=n-1;~j;--j)
					if(!vis[j]&&!vis[(up+k0+j)%n]&&Legal(pos,k0,j,(up+k0+j)%n))
					{
						k1=j,k2=(up+k0+k1)%n,vis[k1]=1,vis[k2]=1;
						if(dfs(pos-1,k0+k1+up>=n))return 1;
						vis[k1]=0,vis[k2]=0,k1=k2=-1;
					}
				return 0;
			}
	else//k0 unknown
		if(k1!=-1)//k1 known
			if(k2!=-1)//k2 known
			{
				if(!vis[(k2-k1-up+n)%n])
				{
					k0=(k2-k1-up+n)%n;vis[k0]=1;
					if(dfs(pos-1,k0+k1+up>=n))return 1;
					vis[k0]=0,k0=-1;return 0;
				}
				else return 0;
			}
			else//k2 unknown
			{
				for(j=n-1;~j;--j)
					if(!vis[j]&&!vis[(up+j+k1)%n]&&Legal(pos,j,k1,(up+j+k1)%n))
					{
						k0=j,k2=(up+k0+k1)%n,vis[k0]=1,vis[k2]=1;
						if(dfs(pos-1,k0+k1+up>=n))return 1;
						vis[k0]=0,vis[k2]=0,k0=k2=-1;
					}
				return 0;
			}
		else//k1 unknown
			if(k2!=-1)
			{
				for(i=n-1;~i;--i)
					for(j=n-1;~j;--j)
						if((i+j+up)%n==k2&&!vis[i]&&!vis[j]&&Legal(pos,i,j,k2))
						{
							vis[k0]=1,vis[k1]=1,k0=i,k1=j;
							if(dfs(pos-1,k0+k1+up>=n))return 1;
							vis[k0]=0,vis[k1]=0,k0=k1=-1;
						}
				return 0;
			}
			else
			{
				for(i=n-1;~i;--i)
					for(j=n-1;~j;--j)
						if(!vis[i]&&!vis[j]&&!vis[(i+j+up)%n]&&Legal(pos,i,j,(i+j+up)%n))
						{
							k0=i,k1=j,k2=(i+j+up)%n;
							vis[k0]=1,vis[k1]=1,vis[k2]=1;
							if(dfs(pos-1,k0+k1+up>=n))return 1;
							vis[k0]=0,vis[k1]=0,vis[k2]=0,k0=k1=k2=-1;
						}
				return 0;
			}
	return 0;
}
int main()
{
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
	register int i,j,k;scanf("%d",&n);
	for(i=0;i<3;++i)scanf("%s",s[i]+1);
	memset(key,-1,sizeof(key));
	dfs(n,0);
}