[Sdoi2010 外星千足虫]高斯消元、位运算压位优化

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1923
【算法分析】
每次相当于加多一个方程组，然后就是高斯消元，但是看着高斯消元那恐怖的复杂度：O(n^3)。
你敢写么。。。
然后我们可以发现，他只有0和1这两种。
这想到了啥？位运算！
我们把方程组的每31位压成1个int类型。
然后消元的时候，一个xor操作，就可以消31个元素！
最后，将除以一个31。
于是可以很快通过。
【时间复杂度】O(m^2*n/32)。
【其它】1A
Orz。。。这次不知道为啥。。。我真的排第一了。。。
而且时间确实比较短。。。
难道是IO的关系？
但是我仅仅用的是scanf么。。。= =
1 24503 edward_mj 1024K 310MS G++ 2.16K 2010-05-19 22:05:42 2 24449 wu3412790 1256K 667MS Pascal 2.59K 2010-05-19 20:39:15 3 24432 maja 1256K 715MS Pascal 2.60K 2010-05-19 20:10:06 4 23270 FDhyc 776K 808MS Pascal 2.32K 2010-05-14 19:26:32 5 23881 gaoxin 872K 965MS Pascal 1.63K 2010-05-17 18:40:25 6 24455 yjq 876K 1013MS Pascal 1.52K 2010-05-19 20:48:03 7 23588 nehzilrz 4056K 1027MS G++ 1.22K 2010-05-16 13:51:32 8 24001 tracyhenry 30356K 1121MS Pascal 1.98K 2010-05-18 13:23:35 9 23657 Apocalypse 808K 2357MS G++ 0.94K 2010-05-16 18:08:46 10 23340 jsn1993 2080K 2372MS G++ 1.16K 2010-05-15 07:53:57 11 23361 oimaster 2064K 2419MS G++ 1.36K 2010-05-15 15:51:45 【CODE】
#include #include #include #include using namespace std;
const int N=2005;
int n,m,ns;
char S[N];
int data[N][N/20],b[N],*a[N],done;
int ans[N];
void output();

void guass(int L){
int i,j,k,step=0,bit=0;
for (i=1;i<=done;i++){
if (a[L][step]&(1< for (j=step;j<=ns;j++)
a[L][j]^=a[i][j];
b[L]^=b[i];
}
bit++; if (bit>31) bit=0,step++;
}
for (i=done+1;i<=L;i++){
k=0;
for (j=i;j<=L;j++)
if (a[j][step]&(1< if (!k) break;
swap(a[i],a[k]);
swap(b[i],b[k]);
done++;
if (done==n) break;
for (j=i+1;j<=L;j++)
if (a[j][step]&(1< for (k=step;k<=ns;k++)
a[j][k]^=a[i][k];
b[j]^=b[i];
}
bit++; if (bit>31) bit=0,step++;
}
}

void solve(){
int i,bit,step,j;
done=0;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++) a[i]=data[i];
for (i=1;i<=m;i++){
scanf("%s",S+1);
scanf("%d",&b[i]);
bit=0; step=0;
for (j=1;j<=n;j++){
a[i][step]|=(int)(S[j]-‘0’)< bit++; if (bit>31) bit=0,step++;
}
ns=step;
guass(i);
if (done==n){
printf("%dn",i);
output();
return;
}
}
printf("Cannot Determinen");
}

void output(){
int i,j,bit,step,now;
ans[n]=b[n];
for (i=n-1;i>=1;i–){
for (j=1;j<=n;j++) S[j]=0;
bit=step=0;
for (j=1;j<=n;j++){
if (a[i][step]&(1< S[j]=(char)(1);
else
S[j]=(char)(0);
bit++; if (bit>31) bit=0,step++;
}
now=0;
for (j=i+1;j<=n;j++)
now^=ans[j]&(int)(S[j]);
ans[i]=now^b[i];
}
for (i=1;i<=n;i++)
if (ans[i]) puts("?y7M#");
else puts("Earth");
}

int main(){
solve();
}