汉明距离相关应用

· · 个人记录

定义：s,t 的汉明距离定义为 \sum_{i=1}^{|s|} [s_i \not = t_i]。

P9187 [USACO23OPEN] Field Day S

给点 n 个长度为 c 的字符串，对每一个字符串找到另外一个字符串，使其汉明距离最大。

观察到 c 很小，围绕值域入手。f_i 表示 i 到最远的目标字符串的最大距离。

考虑建图 x \to x\oplus 2^k 连边，边权为 1，这样要跑最长路。反过来，求最少相同位数，f_i 表示 i 与目标状态的最少相同位数，这样可以直接跑 bfs。

::::info[code]

#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define db double
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f,mod=1e9+7;
const long long INFL=0x3f3f3f3f3f3f3f3f;
const double eps=1e-8;
il int read(){
    int w=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        w=(w<<1)+(w<<3)+(ch^48);
        ch=getchar();
    }
    return w*f;
}
il void chkmax(int &x,int y){x=(x<y)?y:x;}
il void chkmin(int &x,int y){x=(x>y)?y:x;}

const int N=1e5+10,V=18;
int a[N],dis[(1<<V)+10],vis[(1<<V)+10];
int n,c;
int main(){
    #ifndef ONLINE_JUDGE
    //freopen("in.txt","r",stdin);
    #endif
    cin>>c>>n;
    queue<int> Q;
    memset(dis,0x3f,sizeof(dis));
    rep(i,1,n){
        char ch;
        int x=0,y=0;
        rep(j,1,c){
            cin>>ch;
            x=(x<<1)+(ch=='G'),y=(y<<1)+(ch=='H');
        }
        a[i]=x;
        dis[y]=0,Q.push(y);
    }
    while(!Q.empty()){
        int u=Q.front();Q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0;i<c;++i){
            int v=u^(1<<i);
            if(dis[v]>dis[u]+1){
                dis[v]=dis[u]+1;
                Q.push(v);
            }
        }
    }
    rep(i,1,n){
        cout<<c-dis[a[i]]<<"\n";
    }
    #ifndef ONLINE_JUDGE
    fprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);
    #endif
    return 0;
}

::::

CF1186C Vus the Cossack and Strings

一个结论：01 字符串的汉明距离为偶数当且仅当 1 的个数同余。

my_sol。