首页 > 代码库 > 【BZOJ】【1923】【Sdoi2010】外星千足虫
【BZOJ】【1923】【Sdoi2010】外星千足虫
高斯消元解Xor方程组
ZYF Orz
这题……不作死就不会死T^T，用bitset确实比较快，而且可以从string直接转成bitset（构造函数）。
但问题是我把转过来以后的顺序搞反了……原本以为是0~n-1是系数，第n位是方程的结果， 事实上bitset和string里的顺序是反过来的！！！！！
所以输出的时候也需要倒序枚举……
这题我是动态进行高斯消元的……
前k-1个方程已经消元好，然后加入第k个方程进行消元，从高位到低位（我以为是这样，但事实上由于是逆序，所以……不过不要在意这些细节）进行枚举，如果之前的方程里有 这位是1 的方程->消元，否则这个方程就与之前的方程线性无关（或者说就是基的其中之一）
这里需要开一个b[i]保存 “首个为1的位是第i位的方程是第b[i]个” （我语文水平不好……结合代码自己理解）
1 /************************************************************** 2 Problem: 1923 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:200 ms 7 Memory:1524 kb 8 ****************************************************************/ 9 10 //BZOJ 192311 #include<string>12 #include<bitset>13 #include<cstdio>14 #include<cstring>15 #include<cstdlib>16 #include<iostream>17 #include<algorithm>18 #define rep(i,n) for(int i=0;i<n;++i)19 #define F(i,j,n) for(int i=j;i<=n;++i)20 #define D(i,j,n) for(int i=j;i>=n;--i)21 using namespace std;22 const int N=1010;23 bitset<N>a[2020];24 int n,m,cnt=0;25 int b[N];//首个为1的位是第i位的方程是第b[i]个26 bool ans[N];27 void gauss(int now){28 D(i,n,1)29 if (a[now][i]){30 if(b[i]) a[now]^=a[b[i]];31 else {b[i]=now; cnt++; return;}32 }33 }34 int main(){35 ios::sync_with_stdio(false);36 cin >> n >> m;37 string s,ch;38 F(i,1,m){39 cin >>s >> ch;40 s+=ch[0];//所以bitset中1～n保存的是系数，0保存的是结果41 bitset<N> temp(s);42 a[i]=temp;43 gauss(i);44 if (cnt==n){//如果出解了！45 printf("%d\n",i);46 F(j,1,n){47 ans[j]=a[b[j]][0];48 F(k,1,j-1) if (a[b[j]][k]) ans[j]^=ans[k];//回代过程49 }50 D(j,n,1) printf("%s\n",ans[j] ? "?y7M#" : "Earth");51 return 0;52 }53 }54 printf("Cannot Determine\n");55 return 0;56 }
【BZOJ】【1923】【Sdoi2010】外星千足虫
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。