「Bzoj 3508」开灯 (Xor前缀和+BFS+状压DP)

BZOJ 3508
题意：见上。

可以发现这种翻转的题目，如果弄成异或前缀和，那么如果整个序列是0，则灯全灭。
我们相当于将给定要亮着的灯当成初始状态，那么目标就是全关。
考虑异或前缀和两个1就可以消除，用一个BFS算出每个1和其他1消除的代价。
然后之后就是一个两两配对的过程，弄一个状压DP即可。

知识点：
1、异或前缀和

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<complex>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    int n, k, m, a[21], b[100], cf[10000 + 5];
    int cst[21][21], dp[(1 << 21) + 5], dis[10000 + 5];

    void bfs(int ith) {
        ms(dis, 0);
        queue<int > q; q.push(a[ith]);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int i = 1; i <= m; ++i) {
                if (u + b[i] <= n && !dis[u + b[i]]) dis[u + b[i]] = dis[u] + 1, q.push(u + b[i]); 
                if (u - b[i] >= 1 && !dis[u - b[i]]) dis[u - b[i]] = dis[u] + 1, q.push(u - b[i]); 
            }
        }
        for (int i = 1; i <= k; ++i) {
            if (dis[a[i]] == 0) cst[ith][i] = 0x3f3f3f3f;
            else cst[ith][i] = dis[a[i]];
        }
        cst[ith][ith] = 0;
    }

    void clean() {
        ms(cst, 0), ms(dp, 0x3f), ms(cf, 0);
    }
    int solve() {

        clean(); 
        cin >> n >> k >> m; ++n;
        for (int x, i = 1; i <= k; ++i) scanf("%d", &x), cf[x] ^= 1, cf[x + 1] ^= 1;
        for (int i = 1; i <= m; ++i) scanf("%d", &b[i]);
        k = 0;
        for (int i = 1; i <= n; ++i) if (cf[i]) a[++k] = i;
        for (int i = 1; i <= k; ++i) bfs(i);

        dp[0] = 0;
        for (int S = 0; S < (1 << k); ++S) {
            for (int i = 1; i <= k; ++i) {
                if (S & (1 << (i - 1))) continue ;
                for (int j = i + 1; j <= k; ++j) {
                    if ((S & (1 << (j - 1)))) continue ;
                    dp[S | (1 << (i - 1)) | (1 << (j - 1))] = min(dp[S | (1 << (i - 1)) | (1 << (j - 1))], dp[S] + cst[i][j]);
                }
                break;
            }
        }

        if (dp[(1 << k) - 1] == 0x3f3f3f3f) cout << -1 << endl; else
        cout << dp[(1 << k) - 1] << endl;

        return 0;
    }
}
int main() {
    int T; cin >> T;
    while (T--) flyinthesky::solve();
    return 0;
}