第一眼看多条串，比较，那就建个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); } }
[Trie]JZOJ 3231 【佛山市选2013】海明距离
原文：https://www.cnblogs.com/mastervan/p/11107788.html
