34988 Happy Reversal(二进制去取反)

 1 /*
 2    题意：给多个二进制数，对某些数进行按位取反操作！
 3    然后从中找到最大数和最小数，并输出他们的差值！ 
 4    注意：所有的数都是整数，包括取反之后
 5    
 6    思路：一个n为二进制数x，令tmp为n位全1！则 y=tmp&(tmp^x)就是取反之后的数字
 7    将x和y中最大的存放大最大值数组中，最小值存放到最小值数组中！ 
 8    
 9    排序之后，如果最大值数组第一个元素的下标 ！= 最小值数组第一个元素的下标
10    说明这两个最值不是一个数得到的，那么就输出差值！
11    否则最大的差值就是max(最大值数组[2]-最小值数组[1], 最大值数组[1]-最小值数组[2]); 
12 */
13 #include<iostream>
14 #include<cmath>
15 #include<cstdio>
16 #include<cstring>
17 #include<algorithm>
18 #define N 10005
19 using namespace std;
20 struct node{
21    long long nn;      
22    int p; //这个数的下标 
23 };
24 
25 bool cmpMin(node a, node b){
26    return a.nn<b.nn;     
27 }
28 
29 bool cmpMax(node a, node b){
30    return a.nn>b.nn;     
31 }
32 
33 
34 node maxN[N], minN[N];
35 
36 char ch[66];
37 int n, k;
38 
39 int main(){
40    int t, cc=0;
41    scanf("%d", &t);
42    while(t--){
43        scanf("%d%d", &n, &k);
44        long long tmp=0;
45        for(int i=1; i<=k; ++i)
46           tmp=(tmp<<1)+1;
47        
48        for(int i=1; i<=n; ++i){
49           scanf("%s", ch+1);
50           long long xx=0;
51           for(int j=1; j<=k; ++j)
52               if(ch[j]!='0')
53                  xx+=(long long)(pow(2.0, (k-j)*1.0)+0.5);         
54           long long yy=tmp&(xx^tmp);
55           maxN[i].p=minN[i].p=i;
56           maxN[i].nn=max(xx, yy);
57           minN[i].nn=min(xx, yy);
58        }
59        sort(maxN+1, maxN+n+1, cmpMax);
60        sort(minN+1, minN+n+1, cmpMin);
61        printf("Case #%d: ", ++cc);
62        
63        if(n==1) printf("0\n");//不要忘记考虑一个数的时候！ 
64        else if(maxN[1].p!=minN[1].p)
65           printf("%lld\n", maxN[1].nn-minN[1].nn);
66        else printf("%lld\n", max(maxN[2].nn-minN[1].nn, maxN[1].nn-minN[2].nn));
67          
68    }
69    return 0;   
70 }