记录编号	231069	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	Fmuckss	是否通过	通过
代码语言	C++	运行时间	0.099 s
提交时间	2016-02-25 07:42:19	内存使用	0.28 MiB

#include<stdio.h>
#include<iostream>
#include<queue>
using namespace std;
bool use[30];
int refer[30];
int formula[4][30];
int n;
void read() {
	char tmp;
	scanf("%d",&n);
	for(int j = 1; j <= 3; j++){
		for(int i = 1; i <= n; i++) {
			tmp = getchar();
			while(tmp < 'A' || tmp > 'Z') tmp = getchar();
			formula[j][i] = tmp - 'A'+1;
		}
	}
	for(int i = 1; i <= n; i++) {
		refer[i] = -1;
	}
}
bool check_la(int now) {
	for(int i = 1; i <= 3; i++) {
		for(int j = i+1; j <= 3; j++) {
			if(((formula[i][now] != formula[j][now]) && (refer[formula[i][now]] == refer[formula[j][now]])) ||
				((formula[i][now] == formula[j][now]) && (refer[formula[i][now]] != refer[formula[j][now]]))) {
				return false;
			}
		}
	}
	return true;
}
int check_now(int now) {
	int a, b, c;
	bool done = true;
	for(int i = now; i >= 1; i--) {
		a = refer[formula[1][i]]; b = refer[formula[2][i]]; c = refer[formula[3][i]];
		if(a != -1 && b != -1 && c != -1) {
			if(((a+b)%n != c%n) && ((a+b+1)%n != c%n)) {
				return 0;
			}
		} else {
			done = false;
		}
	}
	if(done) return 2;
	return 1;
}
bool dfs(int now, int plus) {
	int cn = check_now(now);
	if(cn == 0) return false;
	else if(cn == 2) return true;
	if(now < n&&!check_la(now+1)) return false;
	if(now <= 0 && !plus) {
		return true;
	}
	int a = refer[formula[1][now]], b = refer[formula[2][now]], c = refer[formula[3][now]];
	if(a != -1) {
		if(b != -1) {
			if(c != -1) {//a,b,c
				if((a+b+plus)%n != c%n) return false;
				else {
					if((a+b+plus >= n ? dfs(now-1, 1) : dfs(now-1, 0))) return true;
				}
			} else {//a,b
				c = a+b+plus;
				if(use[c%n]) return false;
				use[c%n] = true;
				refer[formula[3][now]] = c%n;
				if((c >= n ? dfs(now-1, 1) : dfs(now-1, 0))) return true;
				refer[formula[3][now]] = -1;
				use[c%n] = false;
			}
		} else {
			if(c != -1) {//a,c
				b = c-plus-a;
				if(b >= 0) {
					if(use[b]) return false;
					use[b] = true;
					refer[formula[2][now]] = b;
					if(dfs(now-1, 0)) return true;
					refer[formula[2][now]] = -1;
					use[b] = false;
				} else {
					b += n;
					if(use[b]) return false;
					use[b] = true;
					refer[formula[2][now]] = b;
					if(dfs(now-1, 1)) return true;
					refer[formula[2][now]] = -1;
					use[b] = false;
				}
			} else {//a
				for(int i = n-1; i >= 0; --i) {
					if(use[i]) continue;
					b = i;
					c = a+b+plus;
					if(use[c%n]) continue;
					refer[formula[2][now]] = i;
					refer[formula[3][now]] = c%n;
					use[b] = true;
					use[c%n] = true;
					if(c >= n ? dfs(now-1, 1) : dfs(now-1, 0)) return true; 
					use[c%n] = false;
					use[b] = false;
					refer[formula[3][now]] = -1;
					refer[formula[2][now]] = -1;
				}
			}
		}
	} else {
		if(b != -1) {
			if( c!= -1) {//b,c
				a = c-plus-b;
				if(a>=0) {
					if(use[a]) return false;
					use[a] = true;
					refer[formula[1][now]] = a;
					if(dfs(now-1, 0)) return true;
					refer[formula[1][now]] = -1;
					use[a] = false;
				} else {
					a += n;
					if(use[a]) return false;
					use[a] = true;
					refer[formula[1][now]] = a;
					if(dfs(now-1, 1)) return true;
					refer[formula[1][now]] = -1;
					use[a] = false;
				}
			} else {//b
				for(int i = n-1; i >= 0; --i) {
					if(use[i]) continue;
					a = i;
					c = a+b+plus;
					if(use[c%n]) continue;
					refer[formula[1][now]] = a;
					refer[formula[3][now]] = c%n;
					use[a] = true;
					use[c%n] = true;
					if(c >= n ? dfs(now-1, 1) : dfs(now-1, 0)) return true; 
					use[c%n] = false;
					use[a] = false;
					refer[formula[3][now]] = -1;
					refer[formula[1][now]] = -1;
				}
			}
		} else {
			if(c != -1) {//c
				for(int i = n-1; i >= 0; --i) {
					if(use[i]) continue;
					a = i;
					b = c-plus-a;
					if(b>=0) {
						if(use[b]) continue;
						use[b] = true;
						use[a] = true;
						refer[formula[1][now]] = a;
						refer[formula[2][now]] = b;
						if(dfs(now-1, 0)) return true;
						refer[formula[2][now]] = -1;
						refer[formula[1][now]] = -1;
						use[a] = false;
						use[b] = false;
					} else {
						b += n;
						if(use[b]) continue;
						use[b] = true;
						refer[formula[2][now]] = b;
						if(dfs(now-1, 1)) return true;
						refer[formula[2][now]] = -1;
						use[b] = false;
					}
				}
			} else {//
				for(int i = n-1; i >= 0; --i) {
					if(use[i]) continue;
					a = i;
					for(int j = n-1; j >= 0; --j) {
						if(use[j]) continue;
						b = j;
						c = (a+b+plus)%n;
						if(use[c]) continue;
						use[a] = true;
						use[b] = true;
						use[c] = true;
						refer[formula[1][now]] = a;
						refer[formula[2][now]] = b;
						refer[formula[3][now]] = c;
						if((a+b+plus >= n ? dfs(now-1, 1) : dfs(now-1, 0))) return true;; 
						refer[formula[3][now]] = -1;
						refer[formula[2][now]] = -1;
						refer[formula[1][now]] = -1;
						use[c] = false;
						use[b] = false;
						use[a] = false;
					}
				}
			}
		}
	}
	return false;
}
int main(){
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
	read();
	if(dfs(n,0)) {
		for(int i = 1; i <= n; i++) {
			printf("%d ",refer[i]);
		}
	} else {
		printf("false");
	}
	return 0;
}