辛德瑞拉 戴佩妮,苗华简历,四风回头看自查报告
首先求个前缀异或和，这样就可以\(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;
}
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论