Codeforces79D Password

发表于 | 更新于 | 分类于 | 阅读次数：

Codeforces79D Password

Description

你有$n$个一开始都为灭的灯泡，排成一排

同时你有$l$个长度，分别为$a_1 \sim a_l$

每次你可以选择一段连续子序列，长度为某个$a_i$，将这些灯泡的状态改变（亮变灭，灭变亮）

你可以做任意多次，使得最后有且仅有$k$个位置的灯泡是亮的，这些位置已经给定，为$x_1 \sim x_k$

求最小次数

数据范围

$1 \le n \le 10000,1 \le k \le 10, 1 \le \ l \le 100$

Solution

最短路&&状压，比较巧妙的好题

将原目标序列异或差分，我们会得到偶数个，且不大于$2k$个$1$

考虑每次修改，这不会改变修改区间中间的$01$状态，只会改变首尾，且改变的$1$数量一定是偶数

我们的目标就是通过这样的操作使差分序列中的若干$0$变成$1$

具体考虑修改的影响：设修改区间为$[l, r]$，那么差分序列中会取反的两个位置是$l$和$r + 1$

  1. 如果是两个$1$，那么它们都会变成$0$，这只会纯粹地增加操作次数，没有任何意义
  2. 如果是两个$0$，那么它们都会变成$1$
  3. 如果是一个$1$一个$0$，那它们会交换，本质上是$1$的移动

我们可以发现，上面的$2$操作能让我们得到两个$1$，而$3$操作则能让我们将$1$移动到我们想要的位置上

并且我们还能发现，这里的$1$都是成对出现的，这与差分数组中的“偶数个$1$”这个条件非常契合

即，我们每次选两个为$0$位置将它们变成$1$，若干次之后达到目标状态

考虑到$k$非常小$(\le 10)$，可以考虑用状压枚举状态进行$\texttt{dp}$

具体来说，我们可以钦定一个位置为$1$（这同时会为我们带来另一个$1$），看看它移动到其他位置的最小次数，实现转移

至于最小的操作次数，跑个最短路不就行了吗？

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <queue>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 1e4, M = 21, L = 1e2;
int n, m, l, size, a[L + 5], cnt[1 << M], Dis[N + 5], dis[M + 5][M + 5], dp[1 << M];
bool light[N + 5];
std::vector <int> Vec;
std::queue <int> q;

inline void Bfs(int s) {
	std::memset(Dis, 0x3f, sizeof(Dis));
	q.push(Vec[s]), Dis[Vec[s]] = 0;
	while (q.empty() == false) {
		int u = q.front();
		q.pop();
		for (int i = 1; i <= l; ++i) {
			if (u - a[i] >= 1 && Dis[u] + 1 < Dis[u - a[i]]) {
				Dis[u - a[i]] = Dis[u] + 1;
				q.push(u - a[i]);
			}
			if (u + a[i] <= n + 1 && Dis[u] + 1 < Dis[u + a[i]]) {
				Dis[u + a[i]] = Dis[u] + 1;
				q.push(u + a[i]);
			}
		}
	}
	for (int i = 0; i < size; ++i)
		dis[s][i] = Dis[Vec[i]];
}

int main() {
	scanf("%d%d%d", &n, &m, &l);
	for (int i = 1, pos; i <= m; ++i) {
		scanf("%d", &pos);
		light[pos] = true;
	}
	for (int i = 1; i <= l; ++i)
		scanf("%d", &a[i]);
	std::sort(a + 1, a + 1 + l);
	l = std::unique(a + 1, a + 1 + l) - a - 1;
	for (int i = 1; i <= n + 1; ++i)
		if (light[i] ^ light[i - 1])
			Vec.push_back(i);
	size = (int) Vec.size();
	for (int i = 0; i < size; ++i)
		Bfs(i);
	for (int i = 1; i < 1 << size; ++i)
		cnt[i] = cnt[i ^ (i & -i)] + 1;
	std::memset(dp, 0x3f, sizeof(dp));
	dp[0] = 0;
	for (int i = 0; i < 1 << size; ++i) {
		if (dp[i] == 0x3f3f3f3f || i + 1 == (1 << size)) continue;
		int pos = 0;
		for (; (i & (1 << pos)) != 0; ++pos); // 钦定最右边的0位变为1并找出其位置
		for (int j = pos + 1; j < size; ++j) // 枚举另一个0的位置
			if ((i & (1 << j)) == 0)
				dp[i | (1 << pos) | (1 << j)] = std::min(dp[i | (1 << pos) | (1 << j)], dp[i] + dis[pos][j]);
	}
	printf("%d\n", dp[(1 << size) - 1] == 0x3f3f3f3f ? -1 : dp[(1 << size) - 1]);
	return 0;
}