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

题意描述

对于给定的 个长度为 的序列，使用最小的 次询问区分 序列与其他序列，求 ，无解输出 。

考场二分 + 暴力思路

，直接 dfs 走起！

所以思路是：

1. 如果 n == 1，特判掉，不用问；
2. 枚举每一个序列，并求出区分他的答案；
3. 注意到具有单调性，小 可行大 就一定可行，考虑二分答案 ；
4. 对于给定 进行 dfs 暴力枚举，看看对于特征 问或不问是否能够区分 个（初始化自己能够区分自己）；

总复杂度 ，可以通过这道题目（实际上跑得飞快）。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 25;

int n, m;
int a[MAXN][MAXN];

int man;
bitset<MAXN> differ;

inline bool dfs(int ind, int rest) {
    if (rest == 0 || ind == m + 1)
        return (int)differ.count() == n;
    bool res = false;
    res = res || dfs(ind + 1, rest);
    bitset<MAXN> tmp = differ;
    for (int i = 1; i <= n; ++i) {
        if (a[i][ind] != a[man][ind])
            differ[i] = true;
    }
    res = res || dfs(ind + 1, rest - 1);
    differ = tmp;
    return res;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", &a[i][j]);
    if (n == 1)
        cout << 0, exit(0);
    for (man = 1; man <= n; ++man) {
        differ.reset();
        differ[man] = true;
        int l = 1, r = m + 1;
        while (l < r) {
            int mid = l + ((r - l) >> 1);
            dfs(1, mid) ? r = mid : l = mid + 1;
        }
        cout << (l == m + 1 ? -1 : l) << ' ';
    }
    return 0;
}