Luogu P14032 【MX-X20-T6】「FAOI-R7」超级电话

再遇百万富翁，结果没意识到询问写的是

\mathcal{O}(q2^n)

的光荣倒闭了。

首先考虑

B = 20

该如何处理这个问题。
因为

n = B

，又因为操作是基于二进制，所以可以想到分开每一位去看待。

那就相当于是在

[0, 2^n)

的 01trie 上做这个问题。
能够知道在全局异或的值都为

0

（即

x

均为

0

）时，

[0, y]

能在 trie 上被拆成不超过

n

个满子树。
那如果此时全局异或的值

v

不为

0

呢？能发现也是不超过

n

个满子树，

v

的第

i

位只相当于影响了第

i

层是先取左儿子还是右儿子。

于是建立 trie，维护每个节点的子树信息即可，

A = 2^n - 1

。

似乎后面的表述会有些歧义，这里认为 trie 树更低的层指的是是子树大小越小，该层节点数越多的层。

接下来考虑后面的问题：

B = 5 / 6 / 7

。
此时能够发现 trie 的层数是硬伤，但是为了满足

B

的条件，且依然要基于二进制处理这个问题，我们考虑对 trie 的层进行分块，得到一个压缩后的 trie 树。

具体来说，考虑从高到低每一块分别有

c_1, c_2, \cdots, c_B(c_i\ge 0, \sum c_i = 20)

层，其中第

1

块只有

1

个节点，对于第

i + 1(1\le i\le B)

块，每个第

i

块的节点有

2^{c_i}

个

i + 1

块的儿子，那第

i + 1

块就有

2^{\sum_{j = 1}^i c_j}

个元素。

这样来说就保证了查询时可以每一块至多查询一片，不过这一片该怎么处理呢？
这相当于是对于每个第

i(1\le i\le B)

块的节点，内部还需要建立起一个

[0, 2^{c_i})

的 01trie，并且对于任意全局异或值和选取的个数都需要保存其信息。
看起来似乎所需要的信息数特别多，不过考虑实际分析后（从高到低分析左右子树选取情况）发现信息数仅为

1 + 2\sum\limits_{i = 0}^{c_i - 1} 4^i

，并且因为单独的叶子信息应当是知道的（就是这个节点的各个儿子信息），所以新增的信息数应当为

f(c_i) = 1 + 2\sum\limits_{i = 0}^{c_i - 1} 4^i - 2^{c_i}

。

那么对于

c_{1\sim B}

，所需要的总信息数量就为

\sum\limits_{i = 1}^B\left(2^{\sum_{j = 1}^{i - 1} c_j}\times f(c_i)\right)

。

于是设计一个 dp，

f_{i, j}

表示目前选了

c_{1\sim i}

，

\sum c_k = j

的最小代价。
复杂度为

\mathcal{O}(n^2B)

，在跑出了对应的代价后会发现和题目限制完全一致，那就说明做对了。

如果要看这个的代码放在后面了，输出方案可以得到：

当 $B = 5$ 时， $c_{1\sim 5} = [9, 5, 3, 2, 1]$ 。
当 $B = 6$ 时， $c_{1\sim 6} = [8, 5, 3, 2, 1, 1]$ 。
当 $B = 7$ 时， $c_{1\sim 7} = [8, 4, 3, 2, 1, 1, 1]$ 。

对于实现的部分，应当有很多种方法，我觉得我的写法很逆天，建议不要参考。

对于预处理，我因为不知道怎么表示具体的

(x, y)

对应的信息，所以采取的方案是用 xor-hash 后放到哈希表里处理。

对应的处理顺序就是从低到高做，因为高层的节点需要低层的信息。

在处理块内 trie 的信息时，我是从低到高每次合并相邻的两个子树，具体来说就是维护每个子树的

(v, S)

，其中

v

是整个子树的信息，

S

是整个子树在得到

(x, y)

后可能划分出的信息（不包括整个子树的

v

）。
那么可以知道

(v, S), (u, T)

合并后得到的就是

(v\oplus u, S\cup T \cup (\bigcup_{x\in S} x\oplus u) \cup (\bigcup_{x\in T} v\oplus x)\cup \{u, v\})

。
重复这个操作

c_i

次即可。

对于询问，如果暴力就是

\mathcal{O}(2^n)

复杂度不可接受。
又因为我的做法不能很好的定位，我的做法是首先从高到低定位出每一块，然后在第

i

块中暴力分解这一块所需的信息，这样复杂度就降到了

\mathcal{O}\left(\sum\limits_{i = 1}^n 2^{c_i}\right)

。
这里的暴力分解指的是，直接求出

\{ x\oplus i \mid i\in [0, y)\}

的 xor-hash 值再查表。

两部分的复杂度都不能很好表示出来，能过就对了。

输出方案（这里输出的是压缩 trie 树从低到高的

c_i

）：

CPP

    for (int i = 1; i <= 10; i++) {
        val[i] = 1;
        for (int j = 1, x = 2; j <= i; j++) {
            val[i] += x, x *= 4;
        }
        val[i] -= (1 << i);
    }
    memset(dp, 0x3f, sizeof(dp)), dp[0][0] = 0;
    for (int i = 0; i <= 20; i++) {
        for (int j = 1; i + j <= 20 && j <= 10; j++) {
            for (int k = 0; k < 7; k++) {
                if (chkmin(dp[i + j][k + 1], dp[i][k] + (1ll << i) * val[j])) {
                    lst[i + j][k + 1] = j;
                }
            }
        }
    }

    for (int step : {5, 6, 7}) {
        for (int i = 20, j = step; j; j--) {
            printf("%d ", lst[i][j]);
            i -= lst[i][j];
        }
        puts("");
    }

通过代码：

CPP

#include <bits/extc++.h>

using ull = unsigned long long;

constexpr int maxm = 1e7 + 10;
const std::vector<int> way[8] = {
    {},
    {},
    {},
    {},
    {},
    {1, 2, 3, 5, 9},
    {1, 1, 2, 3, 5, 8},
    {1, 1, 1, 2, 3, 4, 8}
};

int B;

int tot = 1 << 20, totr = 1 << 20;
std::mt19937_64 rand_(std::chrono::steady_clock::now().time_since_epoch().count());
ull rnd[maxm];
__gnu_pbds::cc_hash_table<ull, int> id;
std::vector<int> son[maxm];

void assign(int x, int y, int z);

void init(int n_, int m_, int A_, int B_) {
    B = std::min(B_, 7);

    for (int i = 0; i < (1 << 20); i++) {
        rnd[i] = rand_();
    }

    auto add = [&](ull x, ull y) {
        id[x ^ y] = tot;
        assign(id[x], id[y], tot);
        tot++;
    };
    
    std::vector<std::pair<ull, int>> arr;
    for (int i = 0; i < (1 << 20); i++) {
        arr.emplace_back(rnd[i], i), id[rnd[i]] = i;
    }
    for (int d : way[B]) {
        std::vector<std::pair<ull, int>> newa;
        for (int l = 0; l < arr.size(); l += 1 << d) {
            std::vector<std::pair<ull, std::vector<ull>>> group;
            for (int i = 0; i < (1 << d); i++) {
                son[totr].push_back(arr[l + i].second);
                group.push_back({arr[l + i].first, {}});
            }
            for (int j = 0; j < d; j++) {
                std::vector<std::pair<ull, std::vector<ull>>> newg;
                for (int i = 0; i < group.size(); i += 2) {
                    const auto x = group[i];
                    const auto y = group[i + 1];
                    std::vector<ull> part{x.first, y.first};
                    for (auto val : x.second) {
                        part.push_back(val);
                        add(val, y.first);
                        part.push_back(val ^ y.first);
                    }
                    for (auto val : y.second) {
                        part.push_back(val);
                        add(x.first, val);
                        part.push_back(x.first ^ val);
                    }
                    add(x.first, y.first);
                    newg.push_back({x.first ^ y.first, part});
                }
                group = newg;
            }
            newa.emplace_back(rnd[totr] = group.front().first, totr);
            totr++;
        }
        arr = newa;
    }
}

int all = 0;
inline int conv(int x) {
    return x < (1 << 20) ? (x ^ all) : x;
}
std::vector<int> query(int x, int y) {
    all ^= x, y++;

    if (y == (1 << 20)) {
        return {tot - 1};
    }

    std::vector<int> ans;
    int sum = 20;
    for (int d = B - 1, u = totr - 1; d >= 0; d--) {
        int s = way[B][d];
        sum -= s;
        int xv = (all >> sum) & ((1 << s) - 1);
        int yv = (y >> sum) & ((1 << s) - 1);
        if (yv) {
            ull val = 0;
            for (int i = 0; i < yv; i++) {
                val ^= rnd[son[u][i ^ xv]];
            }
            ans.push_back(conv(id[val]));
        }
        u = son[u][xv ^ yv];
    }
	return ans;
}

Luogu P14032 【MX-X20-T6】「FAOI-R7」超级电话

文章操作

相关推荐

评论

Luogu P14032 【MX-X20-T6】「FAOI-R7」超级电话