洛谷 P2447 [SDOI2010]外星千足虫（高斯消元bitset优化）

传送门

题解

上午才学了高斯，下午准备做几个题实践一下，然后就看见了这个题。。
我看完题，就觉得，这题好裸啊，然后就去看数据范围，发现n<=1000,m<=2000，我就很郁闷，高斯不是 O(n3) 吗？？怎么搞啊？？
然后果断看题解，一看见题解里说bitset，我就知道了，因为矩阵里只会出现0和1，所以可以bitset优化。。
还有就是这题要把加法改成XOR，因为是mod2，所以就是求奇偶性，也就是要用XOR了。
还有，这题输入有毒，getchar会被卡，应该是行末有空格吧。。。
代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m;
int cntm,k;
bitset<1002> a[2001];
bool gauss(){
for(int i=1;i<=n;i++){
int mx=0;
cntm=0;
for(int j=i;j<=m;j++){
if(cntm|=a[j][i]){
mx=j;
break;
}
}
k=max(k,mx);
if(cntm==0){
return 0;
}
if(i!=mx){
swap(a[i],a[mx]);
}
for(int j=1;j<=m;j++){
if(i!=j&&a[j][i]){
a[j]^=a[i];
}
}
}
return 1;
}
int main(){
scanf("%d %d",&n,&m);
char c[1002];
for(int i=1;i<=m;i++){
scanf("%s",c);
for(int j=0;j<n;j++){
a[i][j+1]=c[j]-'0';
}
scanf("%s",c);
a[i][n+1]=c[0]-'0';
}
if(!gauss()){
printf("Cannot Determine");
return 0;
}
else{
printf("%dn",k);
for(int i=1;i<=n;i++){
if(a[i][n+1]){
printf("?y7M#n");
}
else{
printf("Earthn");
}
}
}
return 0;
}

最后

以上就是热情心锁为你收集整理的洛谷 P2447 [SDOI2010]外星千足虫（高斯消元bitset优化）的全部内容，希望文章能够帮你解决洛谷 P2447 [SDOI2010]外星千足虫（高斯消元bitset优化）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。