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

大致题意

这道题要求我们为每个朋友确定最少需要询问多少个特征，才能唯一确定该朋友的身份。具体来说，小

C

需要设计一系列问题（每个问题询问某个特征是否为特定值），使得根据这些问题的答案，能够唯一确定

Miku

心中想的是哪个朋友。

思路

关键点

每个朋友有 $m$ 种特征可以描述。
所有朋友的特征值都是公开的。
对于每个朋友 $i$ ，需要找到最少的特征询问次数。
如果存在与朋友 $i$ 特征完全相同的其他朋友，则无法确定，输出 $- 1$ 。

解题思路
首先对于特殊情况：如果只有一个朋友，不需要任何提问，直接输出 $0$ 。

对于每个朋友 $i$ ：

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

蒟蒻的代码

CPP

#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】心电感应

文章操作

大致题意

思路

蒟蒻的代码

相关推荐

评论

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