bzoj 4689: Find the Outlier

时间：2024-03-28 10:05:32

数据不大，枚举哪个式子错了，对剩下的d+2个式子随意选d+1个高斯消元，然后代入剩下的式子检查是否正确，正确就是那一个式子错了

#include<bits/stdc++.h>

#define il inline

#define vd void

typedef long long ll;

il int gi(){

	int x=0,f=1;

	char ch=getchar();

	while(!isdigit(ch)){

		if(ch=='-')f=-1;

		ch=getchar();

	}

	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();

	return x*f;

}

#define eps 1e-3

double s[11][11];

double S[11];

il vd work(int n){

	for(int i=1;i<=n;++i){

		int t=0;

		for(int j=i;j<=n;++j)if(fabs(s[i][j])>eps)t=j;

		std::swap(s[t],s[i]);

		for(int j=i+1;j<=n;++j){

			if(fabs(s[j][i])<eps)continue;

			for(int k=n+1;k>=i;--k)s[j][k]=s[j][k]*s[i][i]/s[j][i]-s[i][k];

		}

	}

	for(int i=n;i;--i){

		s[i][n+1]/=s[i][i];

		for(int j=1;j<i;++j)s[j][n+1]-=s[j][i]*s[i][n+1];

	}

}

int main(){

#ifndef ONLINE_JUDGE

	freopen("4689.in","r",stdin);

	freopen("4689.out","w",stdout);

#endif

	int d;

	while(scanf("%d",&d),d){

		for(int i=1;i<=d+3;++i)	scanf("%lf",&S[i]);

		for(int i=1;i<=d+3;++i){

			int j=i==1?2:1,cnt=0;

			for(int k=2;k<=d+3;++k)

				if(k!=i&&k!=j){

					++cnt;

					for(int l=1;l<=d+1;++l)s[cnt][l]=pow(k-1,l-1);

					s[cnt][d+2]=S[k];

				}

			work(d+1);

			double sum=0;

			for(int k=1;k<=d+1;++k)sum+=s[k][d+2]*pow(j-1,k-1);

			//printf("%d %.6lf %.6lf\n",i,sum,S[j]);

			if(fabs(sum-S[j])<eps)printf("%d\n",i-1);

		}

	}

	return 0;

}

相关文章