CF637CPromocodes with Mistakes题解
思路概述
这题其实难度不大，完全就是可以暴力水过，大致思路就是以 d i s ( s i , s j ) dis(s_i,s_j) dis(si,sj) 表示 s i s_i si 和 s j s_j sj 不同的数量，那么对于任意 s i s_i si 和 s j s_j sj，一个不合法的k会使得存在 x x x 满足 d i s ( s i , x ) ≤ k , d i s ( s j , x ) ≤ k dis(s_i,x) \leq k,dis(s_j,x) \leq k dis(si,x)≤k,dis(sj,x)≤k，进而 d i s ( s i , s j ) ≤ d i s ( s i , x ) + d i s ( s j , x ) ≤ 2 × k dis(s_i,s_j) \leq dis(s_i,x)+dis(s_j,x) \leq 2 \times k dis(si,sj)≤dis(si,x)+dis(sj,x)≤2×k，故 k ≥ ( d i s ( s i , s j ) + 1 ) ÷ 2 k \ge (dis(s_i,s_j)+1) \div 2 k≥(dis(si,sj)+1)÷2，那么合法的 k k k 就是 k ≤ ( d i s ( s i , s j ) − 1 ) ÷ 2 k \leq (dis(s_i,s_j)-1) \div 2 k≤(dis(si,sj)−1)÷2，故对每个 i , j i,j i,j，更新 ( d i s ( s i , s j ) − 1 ) ÷ 2 (dis(s_i,s_j)-1) \div 2 (dis(si,sj)−1)÷2 的最小值即为答案。
代码部分
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 0x3f3f3f3f
#define maxn 1005
int n;
string s[maxn];
int get(string a,string b)
{
int ans=0;
for(int i=0;i<6;i++)
if(a[i]!=b[i])ans++;
return ans;
}
int main()
{
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i++)
cin>>s[i];
int ans=6;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
ans=min(ans,(get(s[i],s[j])-1)/2);
printf("%d\n",ans);
}
return 0;
}