【题解】Luogu P2447 [SDOI2010]外星千足虫

原题传送门

根据题意，题目给的每个操作就相当于异或上选中的那几只虫子的足数（mod 2）等于0/1

这是一个异或方程组，珂以用高斯消元解出每个虫子的足数（mod 2）、所需最小次数或判断有多解

但是看题目数据范围\(n \leq 1000,m \leq 2000\)，如果直接高斯消元\(O(n^2m)\)的话超时无疑

观察这题的个性：方程组中要通过上下行异或进行消元，这是位运算，一定珂以用bitset优化

我们对每一行开一个bitset，这样消元时直接把两行的bitset异或起来，复杂度为\(O(\frac{n^2m}{\omega})\)

#include <bits/stdc++.h>

#define N 1005

#define M 2005

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    register int x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x*f;

}

inline void write(register int x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

inline int Max(register int x,register int y)

{

	return x>y?x:y;

}

bitset<N> b[M];

int n,m,now,ans;

int main()

{

	n=read(),m=read();

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

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

		{

			char ch=getchar();

			while(ch!='0'&&ch!='1')

				ch=getchar();

			b[i][j]=ch-'0';

		}

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

	{

		now=i;

		while(now<=m&&!b[now][i])

			++now;

		if(now==m+1)

		{

			puts("Cannot Determine");

			return 0;

		}

		ans=Max(ans,now);

		if(now!=i)

			swap(b[i],b[now]);

		for(register int j=1;j<=m;++j)

		{

			if(i==j||!b[j][i])

				continue;

			b[j]^=b[i];

		}

	}

	write(ans),puts("");

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

		if(b[i][n+1])

			puts("?y7M#");

		else

			puts("Earth");

	return 0;

}

巴特西

【题解】Luogu P2447 [SDOI2010]外星千足虫

原题传送门

根据题意，题目给的每个操作就相当于异或上选中的那几只虫子的足数（mod 2）等于0/1

这是一个异或方程组，珂以用高斯消元解出每个虫子的足数（mod 2）、所需最小次数或判断有多解

但是看题目数据范围\(n \leq 1000,m \leq 2000\)，如果直接高斯消元\(O(n^2m)\)的话超时无疑

观察这题的个性：方程组中要通过上下行异或进行消元，这是位运算，一定珂以用bitset优化

我们对每一行开一个bitset，这样消元时直接把两行的bitset异或起来，复杂度为\(O(\frac{n^2m}{\omega})\)

最新文章

热门文章