luogu5283 异或粽子

题目链接

思路

首先求个前缀异或和，这样就可以\(o(1)\)的得到区间异或和了。

然后发现问题转化为

找出不同的\(k\)个二元组\(x,y\)。使得\(a_x \otimes a_y\)的和最大。

有个比较有趣的思路

设\(s_i\)表示前\(i\)个元素的异或和。对于每个\(s_i\),我们找出在\(s\)数组中与他异或起来最大的数字是多少。假设第\(i\)个得到的最大异或和为\(t_i\)

然后从这些数字中找出最大的那个。假设是\(t_x\)。然后我们就把答案加上\(t_x\)，并且把\(t_x\)变为与\(s_x\)异或起来第\(2\)大的异或和。一直这样做下去。

发现可以用堆维护。

发现对于每个异或和都被算了两次。所以把\(k\)先乘\(2\)，并且把最终答案除以\(2\)，就可以了。

代码

/*
* @author: wxyww
* @date:   2019-04-11 19:00:05
* @last modified time: 2019-04-11 19:28:46
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
const int n = 500000 + 100;
ll read() {
    ll x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') {
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9') {
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
struct node {
    ll id;
    int rk;
    ll w;
    node(int x,int y,ll z) {
        id = x,rk = y,w = z;
    }
};
int trie[n * 32][2],cnt[n * 32],tot;
ll a[n];
bool operator < (const node &a,const node &b) {
    return a.w < b.w;
}
priority_queue<node>q;
void insert(ll x) {
    int now = 0;
    for(int i = 31;i >= 0;--i) {
        int k = (x >> i) & 1;
        if(!trie[now][k]) trie[now][k] = ++tot;
        now = trie[now][k];
        cnt[now]++;
    }
}
ll query(ll x,int y) {
    int now = 0;
    ll ret = 0;
    for(int i = 31;i >= 0;--i) {
        int k = (x >> i) & 1;
        if(!trie[now][k ^ 1]) now = trie[now][k];
        else {
            if(y > cnt[trie[now][k ^ 1]]) y -= cnt[trie[now][k ^ 1]],now = trie[now][k];
            else now = trie[now][k ^ 1],ret |= (1ll << i);
        }
    }
    return ret;
}
int main() {
    ll ans = 0;
    int n = read(),k = read() << 1;
    insert(0);
    for(int i = 1;i <= n;++i) {
        a[i] = a[i - 1] ^ read();
        insert(a[i]);
    }
    for(int i = 1;i <= n;++i) q.push(node(a[i],1,query(a[i],1)));
    q.push(node(0,1,query(0,1)));
    while(k--) {
        node tmp = q.top();q.pop();
        ans += tmp.w;
        tmp.rk++;
        tmp.w = query(tmp.id,tmp.rk);

        q.push(tmp);
    }
    cout<<(ans >> 1);
    return 0;
}