JZOJ 3231. 海明距离

妖狐艹你老母 2021-11-30 00:56 254阅读 0赞

# **题目** #

#### Description ####

对于二进制串a，b，他们之间的海明距离是指两个串异或之后串中1的个数。异或的规则为：  
  
0 XOR 0 = 0  
  
1 XOR 0 = 1  
  
0 XOR 1 = 1  
  
1 XOR 1 = 0  
  
计算两个串之间的海明距离的时候，他们的长度必须相同。现在我们给出N个不同的二进制串，请计算出这些串两两之间的最短海明距离。

#### Input ####

第一个数字是整数T（T≤10），代表数据的组数。  
  
接下来有T组数据，每组数据的第一行是一个正整数N，代表不同的二进制串的个数。接下来是N行，每行都是一个二进制串(长度是5)。我们用数字(0-9)和字符(A-F)来表示这个二进制串。它代表这个二进制串的16进制码。例如，“12345”代表的二进制串为“00010010001101000101”。

#### Output ####

对于每个数据，请输出一个整数，即答案值。

#### Sample Input ####

2
    
    2
    
    12345
    
    54321
    
    4
    
    12345
    
    6789A
    
    BCDEF
    
    0137F

#### Sample Output ####

6
    
    7

#### Data Constraint ####

对于30%的数据有1≤N≤100  
  
对于全部数据，有1≤N≤100000

# **分析** #

*  刚开始这道题，我是用快排去跑
 *  后来发现不行，打了个n^2
 *  然后水了个50
 *  后来我直接用1-2^20\*n去跑，发现直接炸
 *  正确解法：
 *  我们要利用1的个数直接去形成数
 *  这样找到一个后就直接可以输出了

# **代码** #

1 #include<iostream>
     2 #include<cmath>
     3 #include<algorithm>
     4 #include<cstdio>
     5 #include<cstring>
     6 #define N 10000000
     7 #define ll long long 
     8 using namespace std;
     9 string s;
    10 int a[N];
    11 int n;
    12 int h[N];
    13 ll tran(string s)
    14 {
    15     ll i,a,b;
    16     double k,h=0;
    17     a=s.length();
    18     b=a-1;
    19     for (i=0;i<=a;i++)
    20     {
    21        if (s[i]<='9'&&s[i]>='0')
    22          s[i]=s[i]-'0';
    23        else if (s[i]<='F'&&s[i]>='A')
    24           s[i]=s[i]-'A'+10;
    25        k=s[i]*pow(16, b);
    26        h+=k;
    27        b--;
    28     }
    29     return h;
    30 }
    31 bool dfs(int x,int y,int l,int r)
    32 {
    33     if (l==r+1)
    34     {
    35         for (int i=1;i<=n;i++)
    36             if (h[a[i]^x]==1) return 1;
    37         return 0; 
    38     } 
    39     for (int i=y+1;i<=20;i++)
    40     {
    41         int m=(1<<i);
    42         if (dfs(x+m,i,l+1,r)) return 1;
    43     }
    44     return 0;
    45 }
    46 int main ()
    47 {
    48     int T;
    49     cin>>T;
    50     while (T)
    51     {
    52         memset(h,0,sizeof(h));
    53         T--;
    54         cin>>n;
    55         for (int i=1;i<=n;i++)
    56         {
    57             cin>>s;
    58             int t=tran(s);
    59             a[i]=t;
    60             h[a[i]]=1;
    61         }
    62         int ans=1;
    63         while (1)
    64           if (dfs(0,-1,1,ans)) break;
    65           else ans++;
    66         cout<<ans<<endl;
    67     }
    68 }

转载于:https://www.cnblogs.com/zjzjzj/p/11112078.html