P9529 一流团子师傅 Super Dango Maker 题解

我们先考虑一次询问具体给了我们什么信息。

实际上，给的是所有颜色的团子中，出现次数最少的那个。

我们希望每次提交一个颜色互不相同的团子组合。

考虑如何找出一个团子组合出来。

首先我们二分一下找到第一个可以凑出来一串团子的前缀。这里一定有一个颜色从 变成了 。我们把这个团子加入。然后继续二分，二分时加入一个前缀和刚刚找出的那个数，找到第一个可以凑出来一个团子的位置，这个肯定是另一个数第一次出现的位置，我们加入这个数，然后继续二分。

直到我们找到了 个数第一次出现的位置，我们报告这个分组。

次数是 次。显然爆炸了。

不过有一件事情是你每次 会减少 ，不过无济于事，次数仍然比 多。

让我们换一个做法。我们可以直接从后往前扫描一遍，如果找到了一个从 变成 的位置就加入这个位置，然后之后询问前缀的时候带上这个位置。

但是这样次数就变成了 了。看上去更劣了。

不过我们其实只需要从每个数都出现一次的最早的位置开始往前扫就可以了。但是可以刻意构造数据让这个位置很晚出现。

但是我们注意到，我们实际上并不需要老老实实按照询问前 小的下表，我们可以询问任意集合。

因此我们可以提前对下标集合随机打乱一下，然后在从最早出现的位置开始从后往前扫。这样就无法构造数据卡掉了。

不过，你还是得知道你的期望次数。不过我们可以写个程序测试一下。

▶

INFO 代码

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace solve {
uint solve(uint n, uint m) {
    std::vector<uint> v;
    for (size_t i = 0; i < m; i++) {
        for (size_t j = 0; j < n; j++) {
            v.push_back(j);
        }
    }

    std::mt19937 rnd(
        std::chrono::steady_clock::now().time_since_epoch().count());

    std::shuffle(v.begin(), v.end(), rnd);

    uint cnt = 0;
    std::vector<bool> vis(n);
    for (size_t i = 0; i < n * m; i++) {
        if (!vis[v[i]]) {
            cnt++;
            vis[v[i]] = true;
        }

        if (cnt == n) {
            return i;
        }
    }
    return 0;
}
} // namespace solve

int main() {
    uint n, m;
    std::cin >> n >> m;
    long double tsum = 0;
    for (size_t j = 0; j < m; j++) {
        ull sum = 0;
        for (size_t i = 0; i < 10000; i++) {
            sum += solve::solve(n, j + 1);
        }
        tsum += (long double)(sum) / 10000;
        std::cout << (long double)(sum) / 10000 << "\n";
    }
    std::cout << tsum << "\n";
    std::cout << std::flush;
}

然后你发现次数就对了。

写一下发现过了。

▶

INFO 代码

#include <algorithm>
#include <array>
#include <chrono>
#include <random>

using uint = unsigned int;
using ll = long long;
using ull = unsigned long long;

namespace solve {
uint query(const std::vector<uint> &x) {
    std::vector<int> xy(x.size());
    for (size_t i = 0; i < x.size(); i++) {
        xy[i] = x[i] + 1;
    }
    return Query(xy);
}

void answer(const std::vector<uint> &x) {
    std::vector<int> xy(x.size());
    for (size_t i = 0; i < x.size(); i++) {
        xy[i] = x[i] + 1;
    }
    Answer(xy);
}

void solve(uint n, uint m) {
    std::mt19937 rnd(
        std::chrono::steady_clock::now().time_since_epoch().count());
    std::vector<uint> rest;
    for (size_t i = 0; i < n * m; i++) {
        rest.push_back(i);
    }

    for (size_t i = 0; i < m; i++) {
        std::shuffle(rest.begin(), rest.end(), rnd);

        auto chk = [&](uint pos, std::vector<uint> p) {
            std::vector<uint> idx;
            for (size_t j = 0; j < pos; j++) {
                idx.push_back(rest[j]);
            }
            for (auto &&j : p) {
                idx.push_back(j);
            }
            return query(idx);
        };

        uint l = 1, r = rest.size() + 1;

        while (l + 1 < r) {
            uint mid = (l + r) / 2;
            if (chk(mid, {})) {
                r = mid;
            }
            else {
                l = mid;
            }
        }

        std::vector<uint> cur;

        l = r;

        for (int j = l - 1; j >= 0; j--) {
            if (!chk(j, cur)) {
                cur.push_back(rest[j]);
            }
        }

        answer(cur);

        std::vector<uint> new_rest;

        for (auto &&j : rest) {
            if (std::find(cur.begin(), cur.end(), j) != cur.end()) {
                continue;
            }
            new_rest.push_back(j);
        }

        rest = new_rest;
    }
    return;
}
} // namespace solve

void Solve(int N, int M) { solve::solve(N, M); }

让我们来分析一下这个次数。

考虑 表示颜色 第一次出现的位置，那么答案是 。

我们做一个 反演。

答案是

考虑 。意思是，一直不放回抽样，直到抽出颜色在集合 中的步数是几。这是负超几何分布。

在这里，一共有 个元素，合格的元素个数有 个，那么期望步数就是 。

证明考虑插板法。 个元素会把序列分成 段，假设第 段的长度是 ，那么我们有

两边加上期望。左边期望线性性质，右侧不随机，所以期望就是自身。

直观上看，每个 的期望应该是相同的。因为对于 的情况，你可以交换 得到另一个合法的 的情况。实际上也是如此。因此每段的期望就是

最后加上 就是这个式子。

然后你发现这个之和集合大小有关，我们进一步化简一下。

就是这个式子。

然后后面的部分我就不会分析了。AI 称这个是 的。

所以总共的复杂度大概是 级别。另外由于 会逐渐减少，并且在小于 的时候会替换 ，所以实际上跑的并不是很满。总共的次数大概是在 左右。