HDU 4712 Hamming Distance（随机算法）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4712

题目大意：任意两个数按位异或后二进制中含1的个数被称为海明距离，给定n个数，求出任意其中两个最小的海明数，输入是16进制。

Sample Input

12345

54321

12345

6789A

BCDEF

0137F

Sample Output

分析：用随机数来模拟，加srand()函数，放置产生伪随机数。代码有2个。

代码1：

 1 # include<iostream>
 2 # include<cstdio>
 3 # include<cstring>
 4 # include<ctime>
 5 # include<cstdlib>
 6 # define INF 0x3f3f3f3f
 7 
 8 using namespace std;
 9 
10 int cmp[16][16];
11 char data[100005][6];
12 
13 int solve(int q,int w)
14 {
15     int a,b,ret=0;
16     for(int i=0; i<5; i++)
17     {
18         char x = data[q][i];
19         char y = data[w][i];
20         if(x>='0' && x<='9')
21             a = x-'0';
22         else
23             a = x-'A' + 10;
24         if(y>='0' && y<='9')
25             b = y-'0';
26         else
27             b = y-'A' + 10;
28         ret += cmp[a][b];
29     }
30     return ret;
31 }
32 int main()
33 {
34     int i,j;
35     for(i=0; i<16; i++)
36     {
37         for(j=0; j<16; j++)
38         {
39             int ans=0;
40             int tmp = i^j;
41             for(int k=0; k<4; k++)
42                 if((1<<k) & tmp)
43                     ans ++;
44             cmp[i][j] = ans;
45         }
46     }
47 
48     int T,n;
49     scanf("%d",&T);
50     while(T--)
51     {
52         scanf("%d",&n);
53         for(i=1; i<=n; i++)
54             scanf("%s",data[i]);
55         int ans = INF;
56         srand((unsigned)time(NULL));
57         for(i=1; i<=60000; i++)
58         {
59             int a = rand()%n + 1;
60             int b = rand()%n + 1;
61             if(a==b)
62                 b= b%n+1;
63             int tmp = solve(a,b);
64             if(tmp < ans)
65                 ans = tmp;
66         }
67         printf("%d
",ans);
68     }
69     return 0;
70 }

代码2：

 1 # include<iostream>
 2 # include<cstdio>
 3 # include<cstring>
 4 # include<ctime>
 5 # include<cstdlib>
 6 # define INF 0x3f3f3f3f
 7 
 8 using namespace std;
 9 
10 int data[100005];
11 
12 int get_one(int x)
13 {
14     int ret = 0;
15     while(x)
16     {
17         ret ++;
18         x = x&(x-1);
19     }
20     return ret;
21 }
22 int main()
23 {
24     srand((unsigned)time(NULL));
25     int T,n,i;
26     scanf("%d",&T);
27     while(T--)
28     {
29         scanf("%d",&n);
30         for(i=0; i<n; i++)
31             scanf("%x",&data[i]);
32         int ans = INF;
33         for(i=100005; i>=0; i--)    //好奇怪，这里从前往后循环返回WA
34         {
35             int a = rand()%n ;
36             int b = rand()%n ;
37             if(a != b)
38                 ans = min(ans,get_one(data[a]^data[b]));
39         }
40         printf("%d
",ans);
41     }
42     return 0;
43 }

HDU 4712 Hamming Distance（随机算法）

相关推荐