第一眼看多條串，比較，那就建個Trie樹
然后一想，不對！怎么搞串中不同的部分呢？
然后就打出了很暴力的每次加串遍歷一遍Trie樹，然后用當前最優(yōu)答案剪枝
跑滿不到O(n^2)，但我覺得會超時
（事實上好像可證時間復(fù)雜度是在小數(shù)據(jù)和大數(shù)據(jù)中優(yōu)，中數(shù)據(jù)表現(xiàn)差的）
小數(shù)據(jù)不用說肯定優(yōu)
大數(shù)據(jù)串多，保證不相同，則不同個數(shù)會減少，減少后遍歷時容易被剪枝剪掉
然后出來一看，數(shù)據(jù)純隨機……欺詐題啊
?
#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