题解：CF79D Password

· · 题解

  • 你有 n 个灯泡，一开始都未点亮。

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

    每次你可以选择一段连续的子序列，且长度为某个 a_i，并将这些灯泡的明灭状态取反。

    求最少的操作次数，使得最后有且仅有 k 个位置是亮的，这些位置已经给定，为 x_1 \sim x_k。

设 n 个灯泡的开关状态为 b_1 \sim b_n。若 b_i = 1 表示第 i 盏灯开启，b_i = 0 表示第 i 盏灯关闭。

第一个观察是，我们从 b_1 = b_2 = \dots = b_n = 0 变化成所有 b_{x_i} = 1 的局面，等价于从所有 b_{x_i} = 1 变化成 b_1 = b_2 = \dots = b_n = 0 的局面。

所以最开始我们让所有 b_{x_i} \gets 1。现在的问题是：

给定 a, b。每次可以选择一个 b 的区间 [x, x + a_i - 1] 取反。求将 b 全部变为 0 的最少操作数。

区间反转用差分维护。令 b 的差分数组为 c_1 \sim c_{n+1}，即 c_i = b_i \operatorname{xor} b_{i-1}。那么将区间 [l, l + a_k - 1] 取反等价于将 c_l, c_{l+a_k} 取反。

显然当 c_1 = c_2 = \dots = c_{n+1} = 0 时，我们的任务就完成了。现在的问题是：

给定 a, c。每次可以选择一个 c 的区间 [x, x + a_i]，并将 c_x, c_{x+a_i} 取反。求将 c 全部变为 0 的最少操作数。

显然我们只需要考虑那些为 1 的位置，即 \{i \mid c_i = 0\}。因为操作 \{i \mid c_i = 1\} 显然是不优的。

若令 g(x, y) 表示将 x, y 同时反转的最小的所需次数。

考虑状压 DP。令 S 表示当前 c 中仍为 1 的下标集合，设 f(S) 表示在状态 S 的情况下，将 c 全部变为 0 的最少操作次数。

转移显然：

f(S) = \min_{u, v \in S}\{f(S/u/v) + g(u, v)\}

答案为 f(\{x \mid c_x = 1\})。

考虑 g(x, y) 的求解。举个例子，如果我们可以同时将 c_x, c_{x+a} 取反，也可以同时将 c_{x+a}, c_{x+a+b} 取反，那么我们就可以通过两次操作，同时将 c_x, c_{x+a+b} 取反。

具体的，考虑建图。对于一条边 u \longleftrightarrow v 表示可以通过一次操作将 u, v 同时取反，那么这张图上 x \to y 的最短路即 g(x,y)。

#include <bits/stdc++.h>

constexpr int N = 10009, K = 22, L = 209;

int n, k, l, x[K], a[L];
bool b[N], c[N];
int mp[L][L];
int Id[N], Di[N], cnt;
int f[1 << K];

struct Gragh {
    int h[N], e[N * L], ne[N * L], idx = 1;

    void add(int a, int b) {
        e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
        e[idx] = a, ne[idx] = h[b], h[b] = idx ++ ;
    }

    int dis[N];
    bool st[N];

    void bfs(int s) {
        std::queue<int> q;
        q.push(s);

        memset(dis, 0x3f, sizeof dis);
        memset(st, 0, sizeof st);

        dis[s] = 0;
        st[s] = true;

        while (q.size()) {
            int u = q.front();
            q.pop();

            for (int i = h[u]; i; i = ne[i]) {
                int v = e[i];
                if (!st[v]) {
                    st[v] = true;
                    dis[v] = dis[u] + 1;
                    q.push(v);
                }
            }
        }

        for (int i = 1; i <= n + 1; ++ i )
            if (c[i]) mp[Di[s]][Di[i]] = dis[i];
    }
}G;

int dp(int S) {
    if (!S) return 0;
    if (f[S]) return f[S];

    int &res = f[S];
    res = 1e9;

    for (int i = 0; i < cnt; ++ i )
        if (S >> i & 1)
            for (int j = 0; j < cnt; ++ j )
                if (S >> j & 1)
                    res = std::min(res, dp(S ^ (1 << i) ^ (1 << j)) + mp[i][j]);

    return res;
}

int main() {
    std::cin >> n >> k >> l;

    for (int i = 1; i <= k; ++ i ) {
        std::cin >> x[i];
        b[x[i]] = true;
    }

    for (int i = 1; i <= n + 1; ++ i ) {
        c[i] = b[i] ^ b[i - 1];
    }

    for (int i = 1; i <= l; ++ i ) {
        std::cin >> a[i];
    }

    for (int i = 1; i <= n + 1; ++ i )
        if (c[i]) Id[cnt ++ ] = i, Di[i] = cnt - 1;

    for (int i = 1; i <= n + 1; ++ i )
        for (int j = 1; j <= l; ++ j )
            if (i + a[j] <= n + 1) G.add(i, i + a[j]);

    for (int i = 1; i <= n + 1; ++ i )
        if (c[i]) G.bfs(i);

    std::cout << (dp((1 << cnt) - 1) == 1e9 ? -1 : f[(1 << cnt) - 1]) << '\n';

    return 0;
}