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

题目链接

题意

有 $n$ 个人，每个人 $m$ 种特征，对于每个人，求出至少询问这个人的几个特征，才能确定是这个人。如果询问所有特征都不能确定，输出 $-1$。

思路

由于需要频繁比较两个人的特征，考虑预处理出第 $i$ 个人和第 $j$ 个人哪些特征有差异。用 $0$ 代表无差异，$1$ 代表有差异。两人所有特征的差异可以用长度为 $m$ 的仅包含 $0$ 和 $1$ 的串表示。

因为 $1\le m\le 20$，可以把差异串压位存储到一个 int 里。用 $\text{diff}_{i,j}$ 储存 $i$ 和 $j$ 的差异串，预处理过程如下：

for(int i=1;i<=n;i++){
  for(int j=1;j<=n;j++){
    if(i==j)continue;
    for(int k=1;k<=m;k++)
      if(a[i][k]!=a[j][k])//i和j的第k个特征有差异
        diff[i][j]|=(1<<(k-1));
  }
}

之后对每个人都进行以下步骤：

设处理到第 $i$ 个人。

枚举所有询问方案：

• 在 $[1,2^m-1]$ 区间内枚举 $k$。二进制下，$k$ 的第 $j$ 位（从右往左）代表是否询问 $i$ 的第 $j$ 个特征值。

• $k$ 在二进制下 $1$ 的个数代表了耗费的询问次数（可以用 __builtin_popcount() 函数计算）。

• 如果询问次数比已经找到的最优解要大，那么它肯定不能成为最优解，continue 退出。

• 遍历所有人（不包括 $i$ 自身）：

  • 如果 $i$ 与这个人的所有差异在此询问方案下都没有被询问到，那么是不能区分这两个人的，break 退出。

• 如果这个方案可以把 $i$ 和其他所有人区分开来，更新最优解。

最后如果一个解都找不到，输出 $-1$，否则输出最优解。

代码如下：

for(int i=1;i<=n;i++){
  int mi=1e9;//储存最优解，初始化为极大值
  for(int k=0;k<(1<<m);k++){//枚举所有询问方案
    int siz=__builtin_popcount(k);//计算询问次数
    if(siz>=mi)continue;
    bool ok=1;
    for(int j=1;j<=n;j++){
    	if(i==j)continue;
    	if((k&diff[i][j])==0){//i与j的所有差异都没有被询问到
    		ok=0;
    		break;
    	}
    }
    if(ok)mi=siz;//更新最优解
  }
  cout<<(mi==1e9?-1:mi)<<' ';
}

完整代码

#include<bits/stdc++.h>
using namespace std;
int n,m,a[22][22],diff[22][22];
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++)
    for(int j=1;j<=n;j++)
      if(i!=j)
        for(int k=1;k<=m;k++)
          if(a[i][k]!=a[j][k])
            diff[i][j]|=(1<<(k-1));
  for(int i=1;i<=n;i++){
    int mi=1e9;
    for(int k=0;k<(1<<m);k++){
      int siz=__builtin_popcount(k);
      if(siz>=mi)continue;
      bool ok=1;
      for(int j=1;j<=n;j++){
      	if(i==j)continue;
      	if((k&diff[i][j])==0){
      		ok=0;
      		break;
      	}
      }
      if(ok)mi=siz;
    }
    cout<<(mi==1e9?-1:mi)<<' ';
  }
  return 0;
}

总结

这题灵活运用了位运算和压位的技巧，并用到了预处理的思想，希望大家愉快地通过本题。