【牛客練習賽 41 D.最小相似度】BFS

D.最小相似度

題意

定義兩個位數相等的二進制串的相似度 S I M ( A , B ) = 二進制串中 A ⊕ B 中0的個數 SIM\left( A,B \right) =\text{二進制串中}A\oplus B\text{中0的個數} SIM(A,B)=二進制串中A⊕B中0的個數

給定 N N N個長度為 M M M的二進制串。

現在的問題是找出一個額外的長度為 M M M的二進制字元串

使得 max ⁡ { S I M ( S 1 , T ) , S I M ( S 2 , T ) . . . S I M ( S N , T ) } \max \left\{ SIM\left( S_1,T \right) ,SIM\left( S_{2,}T \right) ...SIM\left( S_N,T \right) \right\} max{SIM(S1​,T),SIM(S2,​T)...SIM(SN​,T)}最小。

因為滿足條件的可能不止一個,不需要輸出串,隻需要輸出這個最小值即可。

1 ≤ N ≤ 3 ∗ 1 0 5 1 \leq N \leq 3*10^5 1≤N≤3∗105

1 ≤ M ≤ 20 1 \leq M \leq 20 1≤M≤20

做法

由于M隻有20，是以我們知道狀态數一共隻有2^20,我們如果能算出每個狀态和給定n個字元串相似度的最大值，這道題就解決了。首先我們知道所有n個串最初的dp值為m，通過bfs，把每個串丢進隊列一次，每個串改變每一位得到新的字元串，更新那些沒出現過的串的dp值再丢進隊列，就可以保證目前步數為最大相似度。而且保證每個串隻進一次隊列.複雜度就是 O ( 20 ∗ 2 20 ) O(20*2^{20}) O(20∗220)

代碼

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 3e5+5;
char str[maxn][25];
int dp[1<<21];
queue<int>q;
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",str[i]);
    memset(dp,INF,sizeof(dp));
    for(int i=1;i<=n;i++)
    {
        int sta=0;
        for(int j=0;j<m;j++) if(str[i][j]=='1') sta=(sta|(1<<j));
        dp[sta]=m;
        q.push(sta);
    }
    int ans=INF;
    while(!q.empty())
    {
        int tp=q.front();
        q.pop();
        ans=min(ans,dp[tp]);
        for(int j=0;j<m;j++)
        {
            int tmp=(tp^(1<<j));
            if(dp[tmp]==INF)
            {
                dp[tmp]=dp[tp]-1;
                q.push(tmp);
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}