题解：P12407 「CZOI-R3」数字变换

· · 题解

初遇子集动态规划：P12407 「CZOI-R3」数字变换

关键点：

其实，还是 n 的枚举范围太大了，我们可以发现我们只关心之前的状态和目前的状态，这个状态和我们目前的下标有关，还和……还和 x 值本身的大小有关！

做题思路：

  1. 一开始很快写出方程，令 dp_{j, i} 表示操作 j 步使得 a 变成 i，但是时间复杂度很明显是 n 方乘上 m 的，必定超时，于是就引发了上述的思考。
  2. 我们可以发现我们的 x 最大只有 65536，那么我们可以将一开始的循环中枚举 n 的那几层改为枚举 x_i 的大小。
  3. 我们想好这点后，就要对原始的方程做操作，我们令 A_v 表示所有等于 v 的 x 数组对应下标的 dp 值的最小值，那么我们就将原先的转移方程转化为用 A 数组减去双倍的按位求与值。
  4. 现在我们来考虑怎么使后面的那个玩意最小，因为和 k 和 i 有关，所以我们重点关注被改变过一次的 k（在之前我们的 A 数组有涉及到它），可能聪慧的你很快就想到了每次寻找 (A_{v} - 2 \times v) 的最小值，毕竟我们的 v 在减数上，按位求与的结果要么比原数小，要么和原数一样大，嘻嘻，我真聪明；
  5. 不过你很快发现这样写连样例都过不了，因为，如果你看文章很仔细，就会读到我们在之前已经提到过我们的 A 也和 k 有关，你也不知道如果减数 v 变小是否会让 A_v 变得更小，所以你不能只局限于这几个情况中，而是要全部搜索一遍，只要你的减数满足既在 v 的二进制子集中，也要保证在 x_i 的子集中，这样才不会错，而且时间复杂度一直是变成两倍了而已，可以接受。
  6. 我们先考虑贡献的方向和顺序，我们设 r 为按位求与的结果，我们要保证 r 是 v 的子集，这样才能保证我们的结果是可以由 v 和另外一个数按位求与得来的，因为这一关键条件的限制，我们便可以考虑用子集动态规划求，具体实现在代码的第 82 行至 91 行；
  7. 下一步就是我们要考虑那些包括 r 的 x_i，这个就只能反过来用从大集合到小集合的方法寻找，并且查找的对象使我们已经处理过一遍的 A 数组；
  8. 至于，你问我为什么不能反过来先遍历子集到大集合，这个嘛，因为我们的 A_v 直接和 r 相关，所以放在内侧方便编写程序一些。

Code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    register int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
int n, p, k, x[3000009];
int c, y[65536];
int w[2000009][19], L;
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 = 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);
        }
    }
}
int A[3000009], J[3000009], dp[18][200009], G[3000009];
signed main()
{
    n = read();
    p = read();
    k = read();
    c = read();
    seed = read();
    for (int i = 0; i < c; i++)
    {
        y[i] = read();
    }
    get_input();
    for (int i = 1; i <= n; i++)
    {
        L = max(L, x[i]);
    }
    for (int i = 1; i <= n; i++)
    {
        dp[0][i] = 1e18;
    }
    dp[0][p] = 0;
    for (int j = 1; j <= k; j++)
    {
        for (int v = 0; v <= 65536; v++)
        {
            A[v] = 1e18;
        }
        for (int i = 1; i <= n; i++)
        {
            // if (dp[j - 1][i] < 1e18)
            // {
            A[x[i]] = min(A[x[i]], dp[j - 1][i]);
            // }
        }
        for (int j = 0; j < 16; j++)
        {
            for (int k = 0; k <= 65536; k++)
            {
                if ((k >> j) & 1)
                {
                    A[k ^ (1 << j)] = min(A[k ^ (1 << j)], A[k]);
                }
            }
        }
        for (int j = 0; j <= 65536; j++)
        {
            A[j] -= 2 * j;
        }
        for (int j = 0; j < 16; j++)
        {
            for (int k = 0; k <= 65536; k++)
            {
                if ((k >> j) & 1)
                {
                    A[k] = min(A[k ^ (1 << j)], A[k]);
                }
            }
        }

        // for (int o1 = 0; o1 < 16; o1++)
        // {
        //     for (int u =0; u <= 65536; u++)
        //     {
        //         if (u & (1 << o1))
        //         {
        //             G[u] = min(G[u], G[u ^ (1 << o1)]);
        //         }
        //     }
        // }
        for (int i = 1; i <= n; i++)
        {
            dp[j][i] = 2 * L + w[i][j] + A[x[i]];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        cout << dp[k][i] << " ";
    }
    return 0;
}