当前位置：首页 > news >正文

汉明距离相关应用

news 2026/3/26 22:09:05

定义：$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。

#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);#endifcin>>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_JUDGEfprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);#endifreturn 0;
}