[JZOJ4274] [NOIP2015模拟10.28B组] 终章-剑之魂解题报告(二进制)

Description

【背景介绍】
古堡，暗鸦，斜阳，和深渊……
等了三年，我独自一人，终于来到了这里……
“终焉的试炼吗？就在这里吗？”我自言自语道。
“终焉的试炼啊！就在这里啊！”我再一次自言自语道。
“这背后可能有那个东西吗？”我自言自语道。
“这背后一定有那个东西呢！”我又一次自言自语道。
我沉默着，踏上黑漆漆的索桥，小心翼翼地，拿出锋利的注入我灵魂的双剑……
“那么，我们开始吧……”我最后一次自言自语道。

【题目描述】
My soul of my sowrd!
终焉的试炼即将到来，作为一名有修养的剑士，虽然没有习得n刀流但是二刀流还是没问题的。然而我也是个剑的收藏者，家里屯着n把剑，每一把剑都有一个灵魂值a[i]，由于一些剑之间可能有共鸣，所以我需要两把契合度最高的剑。据剑圣所说，两把编号为i,j剑的契合度为a[i] and a[j]。如何深得剑的灵魂呢？
注：AND 为按位与运算，先将数转成二进制，不满位数的补全0，然后成为两个长度相同的二进制数，处理的时候，两个相应的二进制位都为1，该位的结果值才为1，否则为0。例下图。

Input

第一行一个整数n，代表藏剑数。
第二行n个整数，第i个整数表示a[i]。

Output

输出包含一个正整数，最好的两把剑的契合度。

Sample Input

5
12 5 6 3 1

Sample Output

4
【样例解释】
5 and 6=4或者12 and 5=4或者12 and 6=4

Data Constraint

对于40%的数据 n ≤ 1,000
对于100%的数据 n ≤ 1,000,000，0 ≤ a[i] < 2^31

题目大意：给定n个数，从中挑选两个数进行&(and)运算，最大化&值并输出

题解：采取二进制高位到低位的贪心策略，即从高到低能变成1就变成1

那我们就考虑答案的倒数第i位是否可以选。

设当前ans为比第i位高的所有二进制位选择的最优情况的和，那么如果第i位能选，就必定在这n个数中至少有两个数满足:

1.当前答案中的所有二进制为1的位置，在相应的这个数中的位置也为1(即ans&a==ans)；

2.这个数的二进制第i位为1（即a&(2^(i-1)==(2^(i-1))）。

所以，我们只需从高位向低位扫一遍就可以了。

时间：O(30*n)

空间：n

还有不懂的读者手推即可

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

const int maxn=1e6+50;
int n,ans;
int a[maxn];
inline int read()
{
    char ch=getchar();
    int s=0,f=1;
    while (!(ch>='0'&&ch<='9')) {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {s=(s<<3)+(s<<1)+ch-'0';ch=getchar();}
    return s*f;
}
int main()
{
    freopen("sword.in","r",stdin);
    freopen("sword.out","w",stdout);
    n=read();
    for (int i=1;i<=n;i++)
    a[i]=read();
    for (int i=31;i>=0;i--)
    {
        int p=0;
        for (int j=1;j<=n;j++)
        {
            if ((ans&a[j])==ans&&(a[j]&(1<<i))) p++;
            if (p>=2) break;
        }
        if (p>=2) ans+=1<<i;
    }
    printf("%d
",ans);
    return 0;
}