hdu 4712 Hamming Distance（爆搞）

求2<=N<=100000个20位二进制数种汉明码距离最小的点对距离。。。爆搞就行，如果有两个相同的数，那么答案自然是0，当N个数都不相等的时候，从小到大枚举ans，然后枚举长度为20含有1个数为ans的二进制串，依次判断是否有解。看似时间复杂度是2^20*n，但实际效率却还可以。想想，N越大，如果没有相同的数字，那么ans值肯定会越小，所以N=100000的时候，枚举量是不会太大的。

#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<fstream>#include<sstream>#include<bitset>#include<vector>#include<string>#include<cstdio>#include<cmath>#include<stack>#include<queue>#include<stack>#include<map>#include<set>#define FF(i, a, b) for(int i=a; i<b; i++)#define FD(i, a, b) for(int i=a; i>=b; i--)#define REP(i, n) for(int i=0; i<n; i++)#define CLR(a, b) memset(a, b, sizeof(a))#define debug puts("**debug**")#define LL long long#define PB push_back#define eps 1e-10using namespace std;const int maxn = 100010;const int INF = (1<<21) + 10;int T, n, a[maxn];int hash[INF];char ch[10];int calc(char *ch){    int ret = 0;    REP(i, 5)    {        if(isupper(ch[i])) ret = ret*16 + (ch[i]-'A') + 10;        else ret = ret*16 + (ch[i]-'0');    }    return ret;}bool dfs(int val, int now, int len, int num){    if(len == num)    {        REP(i, n) if(hash[a[i]^val] == T) return true;        return false;    }    FF(i, now, 21) if(dfs(val+(1<<i), i+1, len+1, num)) return true;    return false;}int main(){    int ncas;    scanf("%d", &ncas);    for(T=1; T<=ncas; T++)    {        scanf("%d", &n);        bool flag = 0;        REP(i, n)        {            scanf("%s", ch);            a[i] = calc(ch);            if(hash[a[i]] == T) flag = 1;            hash[a[i]] = T;        }        if(flag)        {            puts("0");            continue;        }        int ans = 1;        while(!dfs(0, 0, 0, ans)) ans++;        printf("%d\n", ans);    }    return 0;}

2楼diary_yang5小时前

O(∩_∩)O

1楼u0106971675小时前

玩儿的溜啊，下次比赛的时候能想起来就吊了。。。