记录编号	141422	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]虫食算	最终得分	100
用户昵称	席一鸣	是否通过	通过
代码语言	C++	运行时间	0.574 s
提交时间	2014-12-01 19:26:53	内存使用	0.32 MiB

#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
main()
{
	freopen("alpha.in","r",stdin);
	freopen("alpha.out","w",stdout);
	bool u[26];
	char e[3][26];
	double a[26][26],b[26][26]={0},c[26],t,x[26];
	int i,j,k,n,s;
	cin>>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)]=1;
		}
	}while(s++,i<n);
	for(i=0;i<n;i++)
		cout<<int(x[i]+0.1)<<' ';
}