1 条题解
-
0
【本题解由站长编写】
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
- 上传者