题解 P5283 【[十二省联考2019]异或粽子】

· · 题解

神仙们都写的可持久化Trie然而我并不会写

给一个简单的做法好了QAQ

首先做前缀异或和，然后变成求最大的k对异或和的和

注意到这是一个关于三角(a_i\ xor\ a_j,0\leq i\leq j\leq n)的求值，并且有a_i\ xor\ a_j=a_j\ xor\ a_i所以我们先把答案乘二然后再除回去，这样我们要求的就是最大的2k个有序对，这个就很好处理了.对角线上的元素并不影响，因为a_i\ xor\ a_i=0是最小的.

可以对每一个i求出第t(初始为1)大的a_i\ xor\ a_j，然后把结果扔到堆里，每次取堆顶，然后把堆顶对应的i的第t+1大的a_i\ xor\ a_j扔进堆里.具体看代码好了QAQ.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int N=20000000+10;
struct Node{int id,rk;long long w;bool operator <(const Node &a)const{return w<a.w;}};
priority_queue<Node>q;
long long ans=1,x,s[N];
int a[N][2],size[N],n,m,tot;
void ins(long long x)
{
    int u=0;
    for(int i=31;i>=0;i--)
    {
        int ch=(x>>i)&1;size[u]++;//插入的时候维护子树大小便于处理
        if(!a[u][ch])a[u][ch]=++tot;
        u=a[u][ch];
    }
    size[u]++;
}
long long query(long long x,int rk)
{
    int u=0;long long ans=0;
    for(int i=31;i>=0;i--)
    {
        int ch=(x>>i)&1;//cout<<u<<" "<<ch<<" "<<size[a[u][1]]<<"  ";
        if(!a[u][ch^1])u=a[u][ch];//如果没有和这一位相异的就直接走
        else if(rk<=size[a[u][ch^1]])u=a[u][ch^1],ans|=1LL<<i;//看一下相异节点的子树大小决定走哪边.和平衡树的操作差不多
        else rk-=size[a[u][ch^1]],u=a[u][ch];
    }
    return ans;
}
long long getin()//不开long long见祖宗 我就见祖宗了QAQ
{
    long long x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int main()
{
    n=getin(),m=getin();m<<=1;//前2k个
    for(int i=1;i<=n;i++)x=getin(),s[i]=s[i-1]^x;
    for(int i=0;i<=n;i++)ins(s[i]);//注意有0
    for(int i=0;i<=n;i++)q.push((Node){i,1,query(s[i],1)});//堆中节点存第rk大的s[id]^s[j]
    for(int i=1;i<=m;i++)
    {
        Node t=q.top();ans+=t.w;q.pop();//cout<<t.id<<" "<<t.rk<<" "<<t.w<<endl;
        if(t.rk<n)q.push((Node){t.id,t.rk+1,query(s[t.id],t.rk+1)});
    }
    cout<<(ans>>1)<<endl;//最后把答案除以二
}

可以看到这个代码只有几十行，但是跑得很快.

最后一定一定要开long\ long啊QAQ.