出题人题解 | #最小相似度#

原题解链接：https://ac.nowcoder.com/discuss/157310

此题可以用$FWTFWT$通过，但是出题时的想法是一道$BFSBFS$就可过的题。

$MM$最大只有$2020$，如果把每个二进制串看成一个状态，最多只有$2^{20}=10485762^\{20\}=1\; 048\; 576$个状态。

我们把开始给定的所有二进制串看成起始点，每一步搜索对二进制串进行一个二进制位的翻转对全部状态进行$BFSBFS$，设搜到的步数最大的状态步数为$XX$，则答案就是$M-XM-X$

复杂度$O(N{2}^M)O(N\; 2^M)$

#include<bits/stdc++.h>
using namespace std;
int deep[1<<26];
void solve(){
    queue<int> q;
    int n,m,ans=0;
    char s[30];
    scanf("%d %d",&n,&m);
    memset(deep,-1,sizeof(int)*(1<<(m+1)));
    for(int i=0;i<n;i++){
        scanf("%s",s);
        int f=0;
        for(int j=0;j<m;j++){
            f+=(1<<j)*(s[j]-'0');
        }
        if(deep[f]==-1) {
            deep[f]=0;
            q.push(f);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        ans=max(ans,deep[u]);
        for(int i=0;i<m;i++){
            if(deep[u^(1<<i)]==-1){
                deep[u^(1<<i)]=deep[u]+1;
                q.push(u^(1<<i));
            }
        }
    }
    if(n>300000) printf("!!!\n");
    printf("%d\n",m-ans);
}
int main()
{
    solve();
}