return post swa spa imp scan wap div poj
这题答案就是 2^ 自由元的数目,原因是自由元可以取 1 或者 0,所以就是 ans<<1
由于只要求自由元的数目,所以高斯消元可以直接消后面的,不做前面的了,对答案没有影响
POJ1830 开关问题
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define MAXN 35
using namespace std;
int a[MAXN][MAXN];
int gauss(int m,int n){
int ret=0,line=1;
for(int k=1;k<=m;k++){
int i=line;
while(i<=m){if(a[i][k])break;i++;}
if(i>m){ret++;continue;}//自由元
if(i!=line){for(int j=k;j<=n;j++)swap(a[i][j],a[line][j]);}
for(i=line+1;i<=m;i++){
if(a[i][k]){
for(int j=k;j<=n;j++){
a[i][j]^=a[line][j];
}
}
}
line++;
}
for(int i=line;i<=m;i++)if(a[i][n])return -1;
//最后一定都消成0了,所以a[i][n]必须为0才符合题意
return ret;
}
int n;
void solve(){
memset(a,0,sizeof(a));
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i][n+1]);
int x,y;
for(int i=1;i<=n;i++){scanf("%d",&x);a[i][n+1]^=x;}
for(int i=1;i<=n;i++){a[i][i]=1;}
while(1){
scanf("%d%d",&x,&y);
if(!x&&!y)break;
a[y][x]=1;
}
int ans=gauss(n,n+1);
if(-1==ans)printf("Oh,it's impossible~!!\n");
else printf("%d\n",1<<ans);
}
int main()
{
// freopen("data.in","r",stdin);
int T;
scanf("%d",&T);
while(T--){
solve();
}
return 0;
}
来源: http://www.bubuko.com/infodetail-2459304.html