P12407 「CZOI-R3」数字变换 Solution

· · 题解

锐评一下难度，B 放困难推式子推半天不会做发现 CD 都是简单题，/tuu。再锐评一下出题人怎么不卡暴力枚举子集的 O(3^v) 做法。

dp。定义状态 f_{i,j} 表示操作 i 次恰好变为 j 的最小代价。直接转移那么有：

f_{i,j} = w_{i,j}+ \min_{k=1}^n \{f_{i-1,k}+2(L-(x_k \operatorname{AND} x_i))\}.

略微变形得到：

f_{i,j}=2L + w_{i,j}+\min_{k=1}^n \{f_{i-1, k} - 2 (x_k \operatorname{AND} x_i)\}.

我们应当着手于后面的最小值。注意到这个值只和 x_k 和 x_i 有关。我们记 \operatorname{bit}(x) 表示 x 在二进制下为 1 的位的集合。考虑一下按位与的性质，与得的结果一定是原数的子集，所以我们可以枚举 x_i 与 x_k 的按位与，然后考虑 x_k 转移的贡献。哥们把贡献传到每个子集上，记辅助数组 \displaystyle g_S=\min_{\operatorname{bit}(x_j) = S} f_{i-1,j}，以及 \displaystyle h_T=\min_{T \subseteq S} g_S。那么我们就有转移

f_{i,j} = w_{i,j} + 2L + \min_{T \subseteq \operatorname{bit}(j)} \{h_T-2T\}.

会发现你枚举的 T 不一定恰好等于两个数的与，可能是两个数的与的子集，但这个转移是对的，原因是：假如正确的按位与得到的是 T_0，而枚举到了一个 T_1 \subset T_0，在 h_{T_0}= h_{T_1} 的情况下，显然 2T_0 > 2T_1，后者的转移不优。故转移有正确性。然后做完了。一共 k 层转移，每次转移要枚举子集，设 x_i 的值域为 O(2^v)，如果暴力枚举就是 O(3^v)，如果用 FMT 实现就是 O(v 2^v)，再加上最后转移回到 f 数组还带一个 O(n)。根据实现的不同，总复杂度 O((n+3^v) k) 或者 O((n+v 2^v)k)。

代码是 FMT 版本，和赛时写的暴力枚举子集相比总用时快了六倍。

#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2e5 + 10;
const int V = 16;
int n, K, P, X[N], W[N][11];

namespace RAND {
    int c, y[65536]; unsigned long long seed;
    int get_rand(int mod)
    {
        seed ^= seed << 14;
        seed ^= seed >> 7;
        seed ^= seed << 19;
        seed ^= seed << 23;
        return seed % mod;
    }
    void get_input()
    {
        for (int i = 0; i < c; i ++) cin >> y[i];
        for (int i = 1; i <= n; i++) X[i] = y[get_rand(c)];
        for (int i = 1; i <= n; i++) for (int j = 1; j <= K; j++) W[i][j] = get_rand(1000000);
    }
}

LL DP[11][N], tmp[1 << 16], g[1 << 16]; int popc[1 << 16];

int main() {
    freopen(".in", "r", stdin); freopen(".out", "w", stdout);
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> P >> K >> RAND::c >> RAND::seed; RAND::get_input();
    int mx = 0;
    for (int i = 1; i <= n; i ++) mx = max(mx, X[i]);
    memset(DP, 0x3f, sizeof DP); DP[0][P] = 0;
    for (int i = 1; i <= K; i ++) {
        memset(tmp, 0x3f, sizeof tmp); memset(g, 0x3f, sizeof g);
        for (int j = 1; j <= n; j ++) g[X[j]] = min(g[X[j]], DP[i - 1][j]);
        for (int j = 0; j < V; j ++) for (int k = 0; k < (1 << V); k ++)
            if ((k >> j) & 1) g[k ^ (1 << j)] = min(g[k ^ (1 << j)], g[k]);
        for (int j = 0; j < (1 << V); j ++) g[j] -= 2 * j;
        for (int j = 0; j < V; j ++) for (int k = 0; k < (1 << V); k ++)
            if ((k >> j) & 1) g[k] = min(g[k], g[k ^ (1 << j)]);
        for (int j = 1; j <= n; j ++) DP[i][j] = g[X[j]] + 2 * mx + W[j][i];
    }
    for (int i = 1; i <= n; i ++) cout << DP[K][i] << " \n"[i == n];
    return 0;
}