题解 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. ```cpp #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$.