P2447 [SDOI2010]外星千足虫

怎么说呢？

因为是在mod 2 意义下的吗（一般是遇到二就可能是位运行算或二分图）

就可以利用异或计算。

因为奇数和偶数在二进制上就用判断最后一位就可以了

然后因为异或符合交换律和结合律

直接消元就可以辣

不过对于这个题，输出第一个数字可能是对与我这种蒟蒻的一个挑战。所以，我会在代码中详细的注释

#include<cstdio>

#include<algorithm>

#include<iostream>

#include<bitset>

using namespace std;

char in[52000];

bitset<2010>map[2010];//黑科技

int n,m;

int ans[2010];//记录答案

bool gauss(int &res)//此处为引用

{

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

	{

		int r=i;

		while(!map[r][i]&&r<m+1)

			r+=1;

		if(r==m+1)

			return false;

		else

			res=max(res,r);//从第一个条件一个一个往下找，直到找到一个第i项系数不为零

		if(i!=r)

			swap(map[i],map[r]);//提上来

		for(int j=i+1;j<=m;j++)//注意：这里是把所有条件的第i项全消了

			if(map[j][i])

				map[j]^=map[i];//bitset支持一行与另一行异或

	}

	ans[n]=map[n][n+1];//往回带

	for(int i=n-1;i>=1;i--)

	{

		ans[i]=map[i][n+1];

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

			ans[i]^=(ans[j])*(map[i][j]);//注意系数

	}

	return true;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%s",in+1);

		//printf("%s",in+1);

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

			map[i][j]=in[j]-'0';//bitset可以直接赋值

		int t;

		scanf("%d",&t);

		map[i][n+1]=t;

	}

	int judge=0;//judge是判断到第几个条件就可以求出所有解

	if(!gauss(judge))

	 	printf("Cannot Determine");

	else

	{

		printf("%d\n",judge);

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

		{

			switch(ans[i])

			{

				case 1:printf("?y7M#\n");break;

				case 0:printf("Earth\n");break;

			}

		}

	}

}

巴特西

P2447 [SDOI2010]外星千足虫

最新文章

热门文章