description
两个数的海明距离定义为:这两个数异或所得结果中(1)的个数.给定(n)个数,求最短海明距离
solution
又是一场世纪大暴力.我们构造一数组(v),其值域为((1<<20)).异或是可逆的，根据这一性质，我们可以反过来枚举异或后的值v,v最多有2^20种情况,然后将(v)数组按1的个数从小到大排序,进行最优性剪枝即可完美通过此题.
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<ctime>
#define R register
#define next MabLcdG
#define mod 1
#define debug puts("mlg")
#define Mod(x) ((x%mod+mod)%mod)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
inline ll read();
inline void write(ll x);
inline void writesp(ll x);
inline void writeln(ll x);
const ll maxn=1e5+10;
ll T;
ll n;
ll vocabulary[200];
ll c[maxn];
ll ans;
ll v[(1<<20)],h,rem[(1<<20)];
ll cnt[(1<<20)];
inline ll lowbit(ll x){return x&-x;}
inline void make_v();
inline ll calc(ll x){
ll sum=0;
for(;x;x-=lowbit(x)) ++sum;
return sum;
}
bool vis[(1<<20)];
int main(){
for(R ll i='0';i<='9';i++) vocabulary[i]=i-'0'+1;
for(R ll i='A';i<='F';i++) vocabulary[i]=i-'A'+11;
make_v();
T=read();
while(T--){
memset(vis,0,sizeof vis);
memset(c,0,sizeof c);
n=read();
ans=((ull)1<<63)-1;
for(R ll i=1;i<=n;i++){
for(R ll j=4;j>=0;j--){
char wn=getchar();
while(!vocabulary[wn]) wn=getchar();
c[i]+=(vocabulary[wn]-1)*(1<<(j<<2));
}
for(R ll j=1;j<=h&&rem[j]<ans;j++){
if(vis[(v[j]^c[i])]){
ans=rem[j];break;
}
}
vis[c[i]]=true;
}
writeln(ans);
}
}
inline ll read(){ll x=0,t=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') t=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*t;}
inline void write(ll x){if(x<0){putchar('-');x=-x;}if(x<=9){putchar(x+'0');return;}write(x/10);putchar(x%10+'0');}
inline void writesp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('
');}
inline void make_v(){
for(R ll i1=19;i1>=0;i1--){
v[++h]=(1<<i1);
rem[h]=1;
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
v[++h]=(1<<i1)+(1<<i2);
rem[h]=2;
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3);
rem[h]=3;
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4);
rem[h]=4;
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5);
rem[h]=5;
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6);
rem[h]=6;
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7);
rem[h]=7;
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8);
rem[h]=8;
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9);
rem[h]=9;
}
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10);
rem[h]=10;
}
}
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11);
rem[h]=11;
}
}
}
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12);
rem[h]=12;
}
}
}
}
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13);
rem[h]=13;
}
}
}
}
}
}
}
}
}
}
}
}
}
//14
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14);
rem[h]=14;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
//15
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15);
rem[h]=15;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
//16
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
for(R ll i16=i15-1;i16>=0;i16--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15)+(1<<i16);
rem[h]=16;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
//17
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
for(R ll i16=i15-1;i16>=0;i16--){
for(R ll i17=i16-1;i17>=0;i17--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15)+(1<<i16)+(1<<i17);
rem[h]=17;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
//18
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
for(R ll i16=i15-1;i16>=0;i16--){
for(R ll i17=i16-1;i17>=0;i17--){
for(R ll i18=i17-1;i18>=0;i18--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15)+(1<<i16)+(1<<i17)+(1<<i18);
rem[h]=18;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
//19
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
for(R ll i16=i15-1;i16>=0;i16--){
for(R ll i17=i16-1;i17>=0;i17--){
for(R ll i18=i17-1;i18>=0;i18--){
for(R ll i19=i18-1;i19>=0;i19--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15)+(1<<i16)+(1<<i17)+(1<<i18)+(1<<i19);
rem[h]=19;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
for(R ll i1=19;i1>=0;i1--){
for(R ll i2=i1-1;i2>=0;i2--){
for(R ll i3=i2-1;i3>=0;i3--){
for(R ll i4=i3-1;i4>=0;i4--){
for(R ll i5=i4-1;i5>=0;i5--){
for(R ll i6=i5-1;i6>=0;i6--){
for(R ll i7=i6-1;i7>=0;i7--){
for(R ll i8=i7-1;i8>=0;i8--){
for(R ll i9=i8-1;i9>=0;i9--){
for(R ll i10=i9-1;i10>=0;i10--){
for(R ll i11=i10-1;i11>=0;i11--){
for(R ll i12=i11-1;i12>=0;i12--){
for(R ll i13=i12-1;i13>=0;i13--){
for(R ll i14=i13-1;i14>=0;i14--){
for(R ll i15=i14-1;i15>=0;i15--){
for(R ll i16=i15-1;i16>=0;i16--){
for(R ll i17=i16-1;i17>=0;i17--){
for(R ll i18=i17-1;i18>=0;i18--){
for(R ll i19=i18-1;i19>=0;i19--){
for(R ll i20=i19-1;i20>=0;i20--){
v[++h]=(1<<i1)+(1<<i2)+(1<<i3)+(1<<i4)+(1<<i5)+(1<<i6)+(1<<i7)+(1<<i8)+(1<<i9)+(1<<i10)+(1<<i11)+(1<<i12)+(1<<i13)+(1<<i14)+(1<<i15)+(1<<i16)+(1<<i17)+(1<<i18)+(1<<i19)+(1<<i20);
rem[h]=20;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}
}