题解：P15366 [IOI 2013] Cave

masonxiong · 2026-08-09 22:24:57 · 题解

:::info[简要题面] 有 n(1\le n\le 5000) 个门和开关编号 [0,n)，开关和门一一对应，每个开关都有"上"和"下"两种状态，其中只有一种状态正确，如果处于正确状态则对应的门会打开。你的任务是确定每个开关的正确状态是什么，以及门和开关之间的对应关系。

提供函数 tryCombination(S[])，参数为每个开关的状态，返回所有关闭的门中最小的编号，或者 -1 表示所有门都打开了。此函数至多调用 70000 次。 :::

因为 tryCombination 只会返回关闭的门中最小的编号，所以我们在确定一个门对应的开关和正确状态时应当先将编号比它小的门全部打开来避免影响，于是我们按编号从小到大对于每个门确定它对应的开关和正确状态。

设当前待确定的门为 x，先将 [0,x) 所有门打开，然后将所有未确定的开关置于"上"状态进行一次查询，若结果不为 x 则说明 x 打开了，x 对应的正确状态为"上"；否则为"下"。

接下来确定 x 对应的开关。保持 [0,x) 所有门打开，将剩余开关中一半的状态取反，若查询结果变化说明 x 对应的开关在这一半中，否则在另一半中；无论如何都可以使得候选开关数量减半。

确定一个门所需要的查询次数为 1+\log n，总次数 n+n\log n，时间复杂度 \mathcal O(n^2\log n)。

:::info[code]

#include <bits/extc++.h>

extern "C" int tryCombination(int S[]);

extern "C" void answer(int S[], int D[]);

extern "C" void exploreCave(int N) {
    auto n = static_cast<unsigned>(N);

    std::vector<int> S(n), D(n);
    std::vector<bool> determined(n);

    for (auto x = 0U; x != n; ++x) {
        std::vector<int> currentS(n);
        std::vector<unsigned> undetermined;
        for (auto i = 0U; i != n; ++i)
            determined[i] ? void(currentS[i] = S[i]) : undetermined.push_back(i);

        auto left = 0ULL, right = static_cast<decltype(0ULL)>(undetermined.size());
        auto correct = static_cast<unsigned>(tryCombination(currentS.data())) == x;
        while (right - left > 1) {
            auto middle = (left + right) / 2;
            for (auto i = 0U; i != n; ++i)
                if (!determined[i])
                    currentS[i] = !correct;
            for (auto i = left; i != middle; ++i)
                currentS[undetermined[i]] = correct;
            (static_cast<unsigned>(tryCombination(currentS.data())) == x ? left : right) = middle;
        }

        S[undetermined[left]] = correct;
        D[undetermined[left]] = x;
        determined[undetermined[left]] = true;
    }

    answer(S.data(), D.data());
}

:::