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

**题目大意**：

给定 $n$ 个人各自的 $m$ 种特征，问第 $i$ 个人至少要询问多少个特征才能知道这个人。

**题目思路**：

蒟蒻一开始看到这道题感觉要崩了，感觉是一道 DP。

可当我看到这个我就开心了：$1\le n,m\le 20$。

数据竟然这么水！

那我们便可以使用深搜来解决。

在深搜中我用了一个动态数组来储存需要询问哪些特征（下文所说的遍历的特征均是这个动态数组内的元素）。每当深搜一次开始，我们遍历一遍其他人的特征。假如当前询问的是第 $x$ 个人，若发现第 $i$ 个人的第 $j$ 项特征与第 $x$ 个人的第 $j$ 项特征不同，证明对于第 $i$ 个人是能判断出来的，我们便继续遍历；如果发现这些特征第 $i$ 个人与第 $x$ 个人完全相同，那么证明还不能得出答案，还得继续加特征。当我们发现没有人的这些特征第 $x$ 个人完全相同时，那么我们便打擂台去寻找最小的询问个数，这个个数便是动态数组的长度。

代码如下：

```cpp
#include <bits/stdc++.h>
using namespace std;
int n, m, a[21][21], ans = INT_MAX;
void dfs (int x, int y, vector <pair <int, int> > vv) {
    if (y > m + 1) return ;
    int res = 0;
    if (vv.size ()) {
        for (int i = 1; i <= n; i ++) {
            bool flag = 0;
            if (i != x) { //看看其他人的这些特征有没有与第x个人完全相同
                for (auto& [u, v] : vv) //遍历一下询问数组，看看是否有完全相同
                    if (v != a[i][u]) {
                        flag = 1;
                        break;
                    }
                if (! flag) break;//完全相同，所以这些还不够，得继续加特征
                else res ++;//记成功一次
            }    
        }
        if (res == n - 1) {//若这些特征其他人都没有完全相同的，那么成功，打擂台
            ans = min (int (vv.size ()), ans);
            return ;
        }
    } //下面的部分为取与不取的操作
    vv.push_back ({y, a[x][y]});//取第y个特征
    dfs (x, y + 1, vv);
    vv.pop_back ();//回溯
    dfs (x, y + 1, vv);//不取第y个
}
int main () {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) 
        for (int j = 1; j <= m; j ++) 
            cin >> a[i][j];
    for (int i = 1; i <= n; i ++) {
        ans = INT_MAX;//取最值方便打擂台
        vector <pair <int, int> > null;
        dfs (i, 1, null);
        if (n < 2) cout << 0 << ' ';//这个很重要，不写只能拿90
        else if (ans == INT_MAX) cout << -1 << ' ';//ans没有改变证明没有方案可以判断出第i个人，那么就无解
        else cout << ans << ' ';
    }
}
```

正在渲染内容...