跳至正文

1 条题解

  • 0
    @ 2026-10-7 23:31:07

    【本题解由站长编写】

    n≤8,枚举全部 2^n 种黑白方案:白帽人说真话(他看到的 x 白 y 黑必须与实际相符,看到的数量不含自己),黑帽人说假话(至少一个数不符)。收集所有合法方案,把白帽人的编号按升序拼成数取最小;全黑也合法时输出 0。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    int main() {
        int n;
        cin >> n;
        vector<int> x(n), y(n);
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
        string best = "";
        bool found = false;
        for (int mask = 0; mask < (1 << n); mask++) {
            bool ok = true;
            for (int i = 0; i < n && ok; i++) {
                int sw = 0, sb = 0;
                for (int j = 0; j < n; j++)
                    if (j != i) (mask >> j & 1) ? sw++ : sb++;
                bool truth = (sw == x[i] && sb == y[i]);
                bool white = mask >> i & 1;
                if (white != truth) ok = false;
            }
            if (!ok) continue;
            string num;
            for (int i = 0; i < n; i++) if (mask >> i & 1) num += to_string(i + 1);
            if (num.empty()) num = "0";
            if (!found || num.size() < best.size() || (num.size() == best.size() && num < best)) { best = num; found = true; }
        }
        if (!found) cout << "NoSolution." << endl;
        else cout << best << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4324
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    0
    已通过
    0
    上传者