【JZOJ A组】海明距离

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

思路

记住：骗分最神奇，暴力出奇迹。

异或是可逆的，根据这一性质，我们可以反过来枚举异或后的值S,S最多有2²⁰种情况。

当S^c=d，c为输入中给出的数，如果d也在题目给出的数当中，那么S就是一个合法解。但是实际上，这样做的时间复杂度是O(2²⁰*n),极限数据中，相比算法一，并没有多少优势。所以这个方法是需要优化的。

怎么优化？很容易想到，如果搜索过程中已经得出了最小的解ans，那么当S当中1的个数>=ans时，我们就可以剪枝了。但是，理论复杂度还是O(2²⁰*n)，因为我们不能确保这个剪枝能起很大作用（如果你搜到的答案是从大到小的，那就没办法剪枝了）。所以，我们构造S的次序可以调整一下：按照1的个数从少到多的顺序。那么我们找到了第一个解之后就可以肯定，它就是最终答案。

至于证明……只能说：如果出题人出人工数据来卡暴力的话，并不能使n=10000，ans=20，因为这些数字两两不重复，所以当ans=20，n必定为2。以此类推……极限数据不会太坑。

我这题血亏。。。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=10000077;
int t,n,o,p[N];
ll a[N];
char s[N];
ll change(char *s)
{
	ll x=0,l=strlen(s);
	for(int i=0; i<l; i++) if(isdigit(s[i])) x=x*16+s[i]-'0'; else x=x*16+s[i]-'A'+10;
	return x;
}
bool dfs(int x,int y,int l,int r)
{
	if(l==r+1)
	{
		for(int i=1;i<=n;i++) if(p[a[i]^x]) return 1;
		return 0;
	}
	for(int i=y+1;i<=20;i++)
	{
		int m=(ll)1<<i;
		if(dfs(x+m,i,l+1,r)) return 1;
	}
	return 0;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d",&n),o=0,memset(p,0,sizeof(p));
		for(int i=1;i<=n;i++)
		{
			scanf("%s",s+1),a[i]=change(s+1);
			if(p[a[i]]==1)	
			{
				o=1,printf("0\n");
				for(i++;i<=n;i++) scanf("%*s"); break;
			}	
			p[a[i]]=1;
		}
		if(o) continue;
		int ans=1;
		while(1) if(dfs(0,-1,1,ans)) break; else ans++;
		printf("%d\n",ans);
	}
}