题解 P2962 【[USACO09NOV]灯Lights】

zubizakeli · 2018-03-21 17:18:02 · 题解

说实话我第一眼没看出这是个高斯消元题=-=

所以我用搜索写的qwq

首先，这道题有一个很明显的结论就是每个开关最多只会被操作一次。（因为操作2次等于没有操作）。

我们可以把每个灯看做2进制下的一位，把每个灯的值表示为他所连接到的灯的亦或和，那么开关灯操作就可以看做取亦或操作。

总方案数有2^35个，直接搜索显然会炸，所以我们用meet in the middle，复杂度O（sqrt（2^n））。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
#define LL long long
#define RI register int
using namespace std;
const int INF = 0x7ffffff ;
const int N = 40 ;

inline int read() {
    int k = 0 , f = 1 ; char c = getchar() ;
    for( ; !isdigit(c) ; c = getchar())
      if(c == '-') f = -1 ;
    for( ; isdigit(c) ; c = getchar())
      k = k*10 + c-'0' ;
    return k*f ;
}
int n, m, lv, ans = INF ; LL hh[N] ; LL tt ; LL p1[N], bin[N] ;
bool flag ;
map<LL,int>p ;  // 开不下2^35的数组，其实最多只有2^18个状态，所以用map是可以的

void dfs(int now,LL res,int used) {
    if(now > lv) {
        if(res == tt) {
            ans = min(ans,used) ;
        }
        else {
            if(!flag) {
                int t = p[res] ;
                if(!t || used < t) p[res] = used ;
            } else {
                if(p[tt^res]) ans = min(ans,p[tt^res]+used) ;
            }
        }
        return ;
    }
    dfs(now+1,res^p1[now],used+1) ; dfs(now+1,res,used) ; // 选与不选 
}

int main() {
    n = read(), m = read() ;
    bin[0] = 1 ;
    for(int i=1;i<=n;i++) bin[i] = bin[i-1]<<1 ;
    tt = bin[n] - 1 ;
    memset(hh,0,sizeof(hh)) ;
    LL x, y ;
    for(int i=1;i<=m;i++) {
        x = read(), y = read() ;
        hh[x] ^= bin[y-1], hh[y] ^= bin[x-1] ;
    }
    for(int i=1;i<=n;i++) hh[i] ^= bin[i-1] ;
    lv = n>>1 ;
    for(int i=1;i<=lv;i++) p1[i] = hh[i] ;
    dfs(1,0,0) ;  // 搜索前一半 
    for(int i=1;i<=n-lv;i++) p1[i] = hh[i+lv] ;
    lv = (n+1)>>1 ; flag = 1 ; // flag标记在搜索前半段还是后半段 
    dfs(1,0,0) ;  // 搜索后一半 
    printf("%d",ans) ;
    return 0 ;
}

其实我一开始没有用bin数组，直接用的（1<<x）这种形式，可是（1<<x）好像不能超过int，所以就参考了下黄学长的代码，发现黄学长用bin数组解决了这个问题。