1 条题解

  • 1
    @ 2019-01-08 21:03:30
    /*
    由于位运算不进位的特性
    所以这里可以将每一位单独考虑
    首先将所有数字补成32位二进制的形式(不足则加前导0)
    然后依次将其每一位从高到低的插入trie
    由于要保证最后异或值最大,所以在插入一个数字后,立刻在trie上查找它
    查找时做以下操作:
    若当前位为0,则判断trie里这一位是否有指向1的指针,若存在,则沿着这一条边遍历,否则沿着含0边遍历
    若当前位为1同理
    这样做的依据是:从高到低考虑每一位的时候若不同,则相当于之前有一个数字在这一位上与当前查找数不同,异或后这一位必然为1,在从高到低插入每一位的情况下,结果自然最大。
    将每个局部最大的结果更新答案,就得到了全局最优解。
    */
    #define method_1
    #ifdef method_1
    /*
    
    */
    #include<iostream>
    #include<cstdio>
    #include<algorithm>
    #include<cmath>
    #include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<vector>
    #include<cstring>
    #include<cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=1e5+5;
    const int INF=0x3f3f3f3f;
    ll n,m;
    char a[maxn];
    ll trie[maxn*40][3];
    ll tot=1;
    int ans=0;
    void insert(int val) {
        int p = 1; //因为p从1开始 所以tot初始化为1
        for (int k = 30; k >=0; k--) {
            int ch = val>>k&1;
            if (trie[p][ch] == 0) trie[p][ch] = ++tot;
            p = trie[p][ch];
        }
    }
    
    int search(int val) {
        int p = 1,ans=0; //因为p从1开始 所以tot初始化为1
        for (int k = 30; k >=0; k--) {
            int ch = val>>k&1;
            if(trie[p][ch^1]){
                ans|=1<<k;
                p=trie[p][ch^1];
            }
            else{
                p=trie[p][ch];
            }
        }
        return ans;
    }
    int main() {
        ios::sync_with_stdio(false);
        cin>>n;
        ll x;
        for(int i=1; i<=n; i++) {
            cin>>x;
            insert(x);
            ans=max(ans,search(x));
        }
        cout<<ans;
        return 0;
    }
    #endif
    #ifdef method_2
    /*
    
    */
    
    #endif
    #ifdef method_3
    /*
    
    */
    
    #endif
    
    
    • @ 2019-01-24 18:03:52

      静态建字典树极为巧妙

  • 1

信息

难度
6
分类
(无)
标签
(无)
递交数
85
已通过
22
通过率
26%
被复制
4
上传者