题意：开关上树
见到拿高斯消元胡就行了
#include#include #include #include #include #include using namespace std;typedef unsigned long long ll;const int N=105;inline int read() { char c=getchar(); int x=0, f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int n, u, v;bitset a[N];int now, pivot[N], li[N], val[N];void gauss() { now=1; for(int i=1; i<=n; i++) { int j=now; while(j<=n && !a[j][i]) j++; if(j==n+1) {li[++li[0]] = i; continue;} if(j!=now) swap(a[now], a[j]); for(int j=1; j<=n; j++) if(a[j][i] && j!=now) a[j] ^= a[now]; pivot[i] = now; now++; } now--;}int ans;void dfs(int d, int tot) { //printf("dfs %d %d\n",d,tot); if(d==0) {ans = min(ans, tot); return;} if(tot >= ans) return; if(pivot[d]) { bitset &t = a[pivot[d]]; int x = t[n+1]; for(int i=1; i<=li[0]; i++) if(t[li[i]]) x ^= val[li[i]]; dfs(d-1, tot+x); } else { val[d]=0; dfs(d-1, tot); val[d]=1; dfs(d-1, tot+1); }}int main() { freopen("in","r",stdin); while(true) { n=read(); if(n==0) break; for(int i=1; i<=n; i++) a[i].reset(); memset(pivot, 0, sizeof(pivot)); memset(li, 0, sizeof(li)); ans=n; for(int i=1; i