记录编号	137128	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	Ezoi_XY	是否通过	通过
代码语言	C++	运行时间	0.540 s
提交时间	2014-11-04 08:58:05	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
double a[26][26], b[26][26], x[26], c[26];
bool u[26];
char e[3][26];
int main(){
	freopen("alpha.in", "r", stdin);
	freopen("alpha.out", "w", stdout);
	int i, j, k, n, s(0);
	double t;
	scanf("%d", &n);
	gets(e[0]);
	gets(e[0]); gets(e[1]); gets(e[2]);
	for (i = 0; i < n; ++i){
		b[i][i] = 1;
		++a[i][e[0][i] - 'A']; ++a[i][e[1][i] - 'A']; --a[i][e[2][i] - 'A'];
	}
	for (i = 0; i < n; ++i){
		for (j = i + 1, k = i, t = a[i][i]; j < n; ++j)
			if (fabs(a[j][i]) > fabs(t)) t = a[j][i], k = j;
		if (k != i)
			for (j = 0; j < n; ++j)
				t = a[i][j], a[i][j] = a[k][j], a[k][j] = t,
				t = b[i][j], b[i][j] = b[k][j], b[k][j] = t;
		if (fabs(a[i][i] - 1) > 1e-6)
			for (t = a[i][i], k = 0; k < n; ++k) a[i][k] /= t, b[i][k] /= t;
		for (j = i + 1; j < n; ++j)
			if (fabs(a[j][i]) > 1e-6)
				for (k = 0, t = a[j][i]; k < n; ++k) a[j][k] -= a[i][k] * t, b[j][k] -= b[i][k] * t;
	}
	for (i = n - 1; i >= 0; --i)
		for (j = i - 1; j >= 0; --j)
			if (fabs(a[j][i]) > 1e-6)
				for (k = 0, t = a[j][i], a[j][i] = 0; k < n; ++k) b[j][k] -= t * b[i][k];
	do{
		memset(c, 0, sizeof(c));
		memset(u, 0, sizeof(u));
		memset(x, 0, sizeof(x));
		for (i = 0; i < n - 1; ++i)
			if (s & 1 << i) --c[i], c[i + 1] += n;
		for (i = 0; i < n; ++i){
			for (j = 0; j < n; ++j)
				if (fabs(b[i][j]) > 1e-6 && fabs(c[j]) > 1e-6) x[i] += b[i][j] * c[j];
			if (fabs(x[i] - floor(x[i] + 0.5)) > 1e-6 || x[i] < -1e-6 || x[i] - n + 1 > 1e-6 || u[(int)(x[i] + 0.1)]) break;
			u[(int)(x[i] + 0.1)] = true;
		}
	}while (++s, i < n);
	for (i = 0; i < n - 1; ++i) printf("%d ", (int)(x[i] + 0.1));
	printf("%d\n", (int)(x[n - 1] + 0.1));
	return 0;
}