P13493 【MX-X14-T3】心电感应
思路
大家好，我不会优化，于是我使用暴力通过了这个题。
首先我们有一个很直观的想法是去枚举小 C 问的是哪些人，然后去检验可不可以做到确定答案。
如何判断一种状态是否可行呢？事实上，如果任意一个人，其存在一种状态被询问且这种状态与被锚定的那个人不同，那么这个人就可以被排除了。
按照这个模拟，我们可以得到一个 \(O(n^32^n)\) 的“优秀”算法。考虑优化，发现不会，然后考虑有没有些别的东西可以优化复杂度。
发现我们实际上只需要维护所谓的“判定性问题”，也就是枚举完每一种状态后，我们只需要判定一下是否存在有人在询问的这些特征里与当前枚举的人一模一样。
于是想到什么？bitset！！！
考虑预处理出每一对人之间特征有哪些不一样，用 bitset 存下来。最后在遍历特征的时候遍历判断是否完全包含询问状态，如果包含当前状态就无解。
预处理的复杂度是 \(O(n^3)\)，DP 主体的复杂度是 \(O(\frac{n^32^n}{\omega })\)，其中 $\omega $ 是 32，可以认为是 bitset 自带的优化复杂度。
code
最后记得特判，比如 \(1\times 1\) 的矩阵之类的。
然后喜提最劣解 /kk。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=255;
int n,m,a[N][N],tmp[N];
vector <int> p[N];
bitset <N> t[N][N];
signed main(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);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)continue;for(int k=1;k<=m;k++)if(a[i][k]==a[j][k])t[i][j]^=(1<<(k-1));}if(n==1){cout<<'0';return 0;}for(int k=1;k<=n;k++){int ans=m+1;for(int s=1;s<=(1<<m)-1;s++){int sign=0,cnt=0;vector <int> q;bitset <N> tmp;for(int j=0;j<m;j++)if((s>>j)&1)tmp^=(1<<j),cnt++;for(int i=1;i<=n;i++){if(i==k)continue;bitset <N> now=tmp&t[k][i];if(now==tmp){sign=1;break;}}if(!sign)ans=min(ans,cnt);}if(ans==m+1)cout<<"-1 ";else cout<<ans<<' ';}return 0;
}
结果刚开始写的时候已经比赛开始很久了，一开始又一直在想假的贪心做法获得了 0 分的好成绩。刚写完这道题又被教练叫去运动了，就只写了这一道题（身败名裂了）。