bnu 34988 Happy Reversal

浏览数：19 / 时间：2015年06月11日

Happy Reversal

Elfness is studying in an operation "NOT".

For a binary number A, if we do operation "NOT A", after that, all digits of A will be reversed. (e.g. A=1001101, after operation "NOT A", A will be 0110010).

Now Elfness has N binary numbers of length K, now he can do operations "NOT" for some of his numbers.

Let‘s assume after his operations, the maximum number is M, the minimum number is P. He wants to know what‘s the maximum M - P he can get. Can you help him?

Input

The first line of input is an integer T (T ≤ 60), indicating the number of cases.

For each case, the first line contains 2 integers N (1 ≤ N ≤ 10000) and K (1 ≤ K ≤ 60), the next N lines contains N binary numbers, one number per line, indicating the numbers that Elfness has. The length of each binary number is K.

Output

For each case, first output the case number as "Case #x: ", and x is the case number. Then you should output an integer, indicating the maximum result that Elfness can get.

Sample Input

Sample Output

Case #1: 51
Case #2: 103

Source

2014 ACM-ICPC Beijing Invitational Programming Contest

题解及代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

long long b_2[63];

void init()
{
    b_2[0]=1;
    for(int i=1;i<=60;i++)
    {
        b_2[i]=2*b_2[i-1];
    }
}

long long cal(char s[],int v)
{
    long long ans=0;
    int len=strlen(s);
    int i=0;
    for(int i=0;i<len;i++)
    if(v==1&&s[i]=='1')
    {
        ans+=b_2[len-i-1];
    }
    else if(v==2&&s[i]=='0'){
        ans+=b_2[len-i-1];
    }
    return ans;
}

struct node
{
    int id;
    long long val;
}sn[20010];

bool cmp(node a,node b)
{
    return a.val>b.val;
}
int main()
{
    init();
    int cas,n,k;
    char s[64];
    memset(s,0,sizeof(s));
    scanf("%d",&cas);
    for(int ca=1;ca<=cas;ca++)
    {
        scanf("%d%d",&n,&k);

        for(int i=0;i<n;i++)
        {
            scanf("%s",s);
            sn[i*2].id=sn[i*2+1].id=i;
            sn[i*2].val=cal(s,1);
            sn[i*2+1].val=cal(s,2);
        }
        sort(sn,sn+2*n,cmp);
        printf("Case #%d: ",ca);
        if(n==1)
        {
            printf("0\n");
            continue;
        }

        if(sn[0].id!=sn[2*n-1].id)
        {
            printf("%lld\n",sn[0].val-sn[2*n-1].val);
        }
        else
        {
            printf("%lld\n",max(sn[0].val-sn[2*n-2].val,sn[1].val-sn[2*n-1].val));
        }
    }
    return 0;
}
/*
我们只需要将每个数的本身及它的按位取反的数都求出来就行了。
因为我们不能使用一个数与它的按位取反的数相减，所以我们对两个出身相同的数进行编号。
然后将所有的数进行排序，找到最大的数和最小的数，如果两个数出身不同，那么直接用大数
减去小数就是答案了；如果两数出身相同，那么我们用第二大的数减去最小的数，与最大的数
减去第二小的数进行比较，输出更大者就行了。
*/

bnu 34988 Happy Reversal,,5-wow.com

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

bnu 34988 Happy Reversal