题解：P13493 【MX-X14-T3】心电感应

qrz0226 · 2025-07-26 20:39:39 · 题解

大致题意

这道题要求我们为每个朋友确定最少需要询问多少个特征，才能唯一确定该朋友的身份。具体来说，小 C 需要设计一系列问题（每个问题询问某个特征是否为特定值），使得根据这些问题的答案，能够唯一确定 Miku 心中想的是哪个朋友。

思路

关键点
- 每个朋友有 m 种特征可以描述。
- 所有朋友的特征值都是公开的。
- 对于每个朋友 i，需要找到最少的特征询问次数。
- 如果存在与朋友 i 特征完全相同的其他朋友，则无法确定，输出 - 1 。
解题思路
首先对于特殊情况：如果只有一个朋友，不需要任何提问，直接输出 0 。

对于每个朋友 i：
- 尝试从最少的特征数量 k=1 开始，逐步增加到 m 。
- 对于每个 k 值，枚举所有可能的 k 个特征组合。
- 检查该特征组合是否能唯一区分朋友 i 与其他所有朋友。
- 一旦找到有效的特征组合，记录 k 值并停止尝试更大的 k 值。
- 如果尝试了所有特征组合仍无法区分，则输出 - 1 。
  蒟蒻的代码
```
#include <iostream>
#include <vector>
using namespace std;
```

int main() { int n, m; cin >> n >> m;

vector<vector<int>> a(n, vector<int>(m));
for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
        cin >> a[i][j];
    }
}

// 特殊情况处理：如果只有一个朋友，不需要任何提问
if (n == 1) {
    cout << 0 << endl;
    return 0;
}

for (int i = 0; i < n; i++) {
    int oemornora = -1;

    // 尝试从最少的特征数量开始
    for (int k = 1; k <= m; k++) {
        // 标记是否找到合适的特征组合
        bool found = false;

        // 枚举所有可能的特征组合
        for (int mask = 1; mask < (1 << m); mask++) {
            if (__builtin_popcount(mask) != k) continue;

            // 检查该组合是否能唯一识别第i个朋友
            bool valid = true;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;

                // 检查朋友j与i在所选特征上是否完全相同
                bool isSame = true;
                for (int t = 0; t < m; t++) {
                    if (mask & (1 << t)) {  // 如果选择了特征t
                        if (a[i][t] != a[j][t]) {
                            isSame = false;
                            break;
                        }
                    }
                }

                // 如果存在另一个朋友与i在所选特征上完全相同，则该组合无效
                if (isSame) {
                    valid = false;
                    break;
                }
            }

            if (valid) {
                oemornora = k;
                found = true;
                break;
            }
        }

        if (found) break;
    }

    cout << oemornora << " ";
}

cout << endl;
return 0;

}

题解：P13493 【MX-X14-T3】心电感应

大致题意

思路

蒟蒻的代码