记录编号	442775	评测结果	AAAAWAAAWW
题目名称	[NOIP 2004]虫食算	最终得分	70
用户昵称	Imone NOI2018Au	是否通过	未通过
代码语言	C++	运行时间	10.544 s
提交时间	2017-08-28 16:08:59	内存使用	0.29 MiB

#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;

typedef int matrix[27][27];
inline bool gauss(matrix M, int n) {
	int i, r, c;
	for(i=0;i<n;i++) {
		r = i;
		while(!M[r][i] && r < n) r++;
		if(!M[r][i]) return 0;
		if(r != i) for(c=i;c<=n;c++) swap(M[r][c], M[i][c]);
		
		int t = M[i][i];
		for(r=i+1;r<n;r++) {
			int p = M[r][i];
			for(c=i;c<=n;c++) M[r][c] = M[r][c] * t - M[i][c] * p;
		}
	}
	for(i=n-1;i>=0;i--) {
		for(c=i+1;c<n;c++) M[i][n] -= M[i][c] * M[c][n];
		M[i][n] /= M[i][i];
	}
	return 1;
}

int N;
const int MAXN = 30;
char A[MAXN], B[MAXN], C[MAXN];
bool vis[MAXN];
matrix M;

inline void rev(char *s) {
	int i;
	for(i=0;i<N/2;i++) swap(s[i], s[N-i-1]);
	for(i=0;i<N;i++) s[i] -= 'A';
}

int main() {
	freopen("alpha.in", "rt", stdin);
	freopen("alpha.out", "wt", stdout);

	scanf("%d%s%s%s", &N, A, B, C);
	rev(A); rev(B); rev(C);

	int i, set, full = (1 << (N - 1)) - 1;
	for(set=0;set<=full;set++) {
		memset(M, 0, sizeof(M));
		for(i=0;i<N;i++) {
			if((set >> i) & 1) M[i][N] += N;
			if(i && ((set >> (i - 1)) & 1)) M[i][N] -= 1;
			
			M[i][A[i]]++;
			M[i][B[i]]++;
			M[i][C[i]]--;
		}
		if(gauss(M, N)) {
			bool ok = 1;
			memset(vis, 0, sizeof(vis));
			for(i=0;i<N;i++) {
				if(M[i][N] < 0 || M[i][N] >= N || vis[ M[i][N] ]) { ok = 0; break; }
				vis[ M[i][N] ] = 1;
			}
			if(ok) {
				for(i=0;i<N;i++) printf("%d ", M[i][N]);
				break;
			}
		}
	}
	return 0;
}