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

Sample Output

6
7

Data Constraint

对于30%的数据有1≤N≤100

对于全部数据，有1≤N≤100000

分析

第一眼看多条串，比较，那就建个Trie树

然后一想，不对！怎么搞串中不同的部分呢？

然后就打出了很暴力的每次加串遍历一遍Trie树，然后用当前最优答案剪枝

跑满不到O(n^2)，但我觉得会超时

（事实上好像可证时间复杂度是在小数据和大数据中优，中数据表现差的）

小数据不用说肯定优

大数据串多，保证不相同，则不同个数会减少，减少后遍历时容易被剪枝剪掉

然后出来一看，数据纯随机……欺诈题啊

#include <iostream>#include <cstdio>#include <cstring>#include <memory.h>using namespace std;const int N=1e5 10;int T,n;int a[N],b[21],t[2097153][2],end[2097153];int cnt,calc,lans;void Find(int k,int x,int dep) {    if (end[x])    {        lans=calc;        return;    }    if (calc>=lans) return;    for (int i=0;i<2;i  )        if (t[x][i]) {            if (b[dep 1]!=i) calc  ;            Find(k,t[x][i],dep 1);            if (b[dep 1]!=i) calc--;        }}void Insert(int k) {    int now=0;    for (int i=1;i<=20;i  ) {        if (!t[now][b[i]]) now=t[now][b[i]]=  cnt;        else now=t[now][b[i]];    }    end[now]=1;}int main() {    for (scanf("%d",&T);T;T--) {        scanf("%d",&n);        memset(t,0,sizeof t);lans=2147483647;cnt=0;memset(end,0,sizeof end);        for (int i=1;i<=n;i  ) {            char c[10];            scanf("%s",c 1);            int len=strlen(c 1);            a[i]=0;            for (int j=1;j<=len;j  )                if (c[j]>='0'&&c[j]<='9') a[i]=a[i]*16 c[j]-'0';                else a[i]=a[i]*16 c[j]-'A' 10;            for (int j=1;j<=20;j  ) b[20-j 1]=a[i]%2,a[i]/=2;            Find(i,0,0);            Insert(i);        }        if (n==1) printf("0\n");        else printf("%d\n",lans);    }}

View Code

来源：https://www.icode9.com/content-4-281651.html

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。