JDOJ-2176: 最富有的人

[文章目录]

Description

你经过了一段时间的打工,老板带你来到了他的私人金库。
在你的面前有n堆金子,老板要求你只能选择其中的两堆,而你的工资为这两堆金子价值的xor值,你想成为最富有的人,你就要做出最优的选择。
名词解释:
xor运算,两个数的对应二进制位相同则答案的二进制该位为0,不同则为1,例如10的二进制表示为1010,5的二进制表示为101,15的二进制表示为1111,则10 xor 5 = 15,当然,xor运算满足交换律,即5 xor 10 = 15。
xor运算通常用于对二进制的特定一位进行取反操作,因为异或可以这样定义:0和1异或0都不变,异或1则取反。
xor运算的逆运算是它本身,也就是说两次异或同一个数最后结果不变,即(a xor b) xor b = a。
xor运算可以用于简单的加密。【比如我想对我MM说1314520,但怕别人知道,于是双方约定拿我的生日19961008作为密钥。1314520 xor 19961008 = 19176040,我就把19176040告诉MM。MM再次计算19176040 xor 19961008的值,得到1314520,于是她就明白了我的企图。

搞一个trie树,每次拿出来一个数,上trie树跑一遍,如果有不同的就累加,如果没有不同的就将就。然后就找到最大解啦。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int read()
{
    char ch=getchar();int re=0;
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9')
        re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
    return re;
}
int nxt[3001000][2];
int t,n,val,root=1,tot;
long long ans;
void insert(int id,int x)
{
    long long re=0;
    int flag;
    for(int i=30;i>=0;i--)
    {
        flag=(x&(1<<i)) ? 0:1;
        if(nxt[id][flag]) id=nxt[id][flag],re+=(1ll<<i);
        else id=nxt[id][flag^1];
    }
    ans=max(ans,re);
}
void trie(int id,int x)
{
    int flag;
    for(int i=30;i>=0;i--)
    {
        flag= (x&(1<<i)) ? 1:0;
        if(!nxt[id][flag]) nxt[id][flag]=++tot,nxt[tot][1]=nxt[tot][0]=0;
        id=nxt[id][flag];
    }
}
int main()
{
    t=read();
    while(t--)
    {
        ans=0;
        nxt[root][0]=nxt[root][1]=0;
        tot=1;
        n=read();
        trie(root,read());
        for(int i=2;i<=n;i++)
        {
            val=read(); 
            insert(root,val);
            trie(root,val);
        }
        printf("%lld\n",ans);
    }
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注