【BZOJ3508】开灯

题面

bzoj

题解

其实变为目标操作和从目标操作变回来没有区别，我们考虑从目标操作变回来。

区间整体翻转（\(\text{Xor}\;1\)）有点难受，我们考虑将这个操作放在差分数组上，也就是说令\(a\)为原数组，\(c\)为差分数组，\(c_i=a_{i-1}\text{Xor}\;a_i\)。

那么我们就相当于让差分数组上的数全变为\(0\)，而一次操作就相当于让一对\(1\)消掉或一对\(0,1\)位置互换。

而两个\(1\)在其他位置消掉和在某个\(1\)的位置消掉是没有区别的，多个\(1\)也一样，所以我们可以直接\(bfs\)预处理每对点消掉的贡献。

而差分数组最多\(2K\)个\(1\)，状压每个点有没有被消掉即可。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (ch != '-' && (ch > '9' || ch < '0')) ch = getchar();

    if (ch == '-') w = -1 , ch = getchar();

    while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();

    return w * data;

}

const int INF = 0x3f3f3f3f;

const int MAX_N = 40005, MAX_M = 105;

int N, K, M;

int b[MAX_M];

bool used[MAX_N], g[MAX_N];

int st[30], tp;

int cost[30][30], dep[MAX_N];

queue<int> que;

void bfs(int s, int *dis) {

	memset(dep, 0, sizeof(dep));

	dep[s] = 1;

	que.push(s);

	while (!que.empty()) {

		int x = que.front(); que.pop();

		for (int i = 1; i <= M; i++) {

			if (x + b[i] <= N && !dep[x + b[i]]) dep[x + b[i]] = dep[x] + 1, que.push(x + b[i]);

			if (x - b[i] >= 1 && !dep[x - b[i]]) dep[x - b[i]] = dep[x] + 1, que.push(x - b[i]);

		}

	}

	for (int i = 0; i < tp; i++) dis[i] = dep[st[i]] - 1;

}

int f[1 << 20];

int main () {

#ifndef ONLINE_JUDGE

	freopen("cpp.in", "r", stdin);

#endif

	int Q = gi();

	while (Q--) {

		memset(used, 0, sizeof(used)); tp = 0;

		N = gi() + 1, K = gi(), M = gi();

		for (int i = 1; i <= K; i++) used[gi()] = 1;

		for (int i = 1; i <= M; i++) b[i] = gi();

		for (int i = 1; i <= N; i++) g[i] = used[i] ^ used[i - 1];

		for (int i = 1; i <= N; i++) if (g[i]) st[tp++] = i;

		for (int i = 0; i < tp; i++) bfs(st[i], cost[i]);

		memset(f, 0x3f, sizeof(f));

		f[0] = 0;

		for (int S = 0; S < (1 << tp) - 1; S++) {

			for (int i = 0; i < tp; i++) {

				if (S >> i & 1) continue;

				for (int x = i + 1; x < tp; x++) {

					if ((S >> x & 1) == 0 && (cost[i][x] != -1)) {

						int tmp = (S | (1 << i) | (1 << x));

						f[tmp] = min(f[tmp], f[S] + cost[i][x]);

					}

				}

				break;

			}

		}

		printf("%d\n", f[(1 << tp) - 1] == INF ? -1 : f[(1 << tp) - 1]);

	}

	return 0;

}