洛谷题单指南-字符串-P5283 [十二省联考 2019] 异或粽子

原题链接：https://www.luogu.com.cn/problem/P5283

题意解读：n个整数，每次从从取l~r的数进行异或得到美味值，一共取k次，并计算这k个美味值之和的最大值。

解题思路：

1、如何O(1)的计算l~r数的异或，得到美味值

可以借助前缀和思想，a[i]为第i个数，s[i]表示a[1]~a[i]每个数的异或值，要计算l~r的异或值，只需要s[r]^s[l-1]即可。

因此，一个美味值就是从s[0]~s[n]中任意挑两个值s[i],s[j],i<j进行异或！

2、如何计算k个美味值之和的最大值

美味值既然是从s[0]~s[n]任意挑两个值进行异或，那么可以将s[]中两个数的异或值最大的前k个计算出来，然后求和即可。

计算两个数异或的最大值是一个经典问题，可以借助Trie树来实现。

但是这里，需要计算的是异或值第k大的数，并且s[i]、s[j]的最大异或值是对称的。

对于异或值对称的问题，可以不必特别处理，只用把k扩大2倍，计算前2k个最大的异或值，然后加起来，结果除以2即可。

关键问题只剩一下一个：如何计算与一个数异或第k大的值？思路如下：

在对每个数建立trie树时，记录每个结点所承载的数的个数,

在查找与一个数x异或第k大的数时，我们根据异或相反更大的原则，如果相反路径上的节点承载的数的个数大于等于k，那么就走相反路径,

如果相反路径上的节点承载的数的个数小于k，那么第k大的数一定在另一条路径上，同时将要查找的第k个数减去相反路径承载的数的个数。

要找到最大的2k个异或值，先求n个数每个数异或第k大值（初始k=1），存入优先队列，每次取队头(异或值最大者)，然后计算与队头那个数异或第k+1大值放入优先队列，直到取出2k个数为止。

语言有点绕，看代码会更好理解。

注意数字的取值范围，全程long long。

100分代码：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 500005;
int n, k;
ll a[N], s[N];
int son[N * 32][2], idx, w[N * 32]; //w存储每个结点所承载的数的个数

struct Node
{
    int x; //第x个数
    int th; //与第x个数异或第th大的值
    ll val; //异或值

    bool operator < (const Node &node) const
    {
        return val < node.val; //val大的在堆顶
    }
};
priority_queue<Node> q;
ll ans;

void add(ll val)
{
    int u = 0;
    for(int i = 31; i >= 0; i--)
    {
        int v = (val >> i) & 1; //从高到低取val的二进制位
        if(!son[u][v]) son[u][v] = ++idx;
        u = son[u][v];
        w[u]++;
    }
}

//查找与val异或第th大的结果
ll find(ll val, int th)
{
    int u = 0;
    ll res = 0;
    for(int i = 31; i >= 0; i--)
    {
        int v = (val >> i) & 1; //从高到低取val的二进制位
        if(w[son[u][!v]] >= th) //如果与当前二进制位相反的路径存在超过th个数就优先走这条路径
        {
            u = son[u][!v];
            res = 2 * res + 1; //相反的二进制异或得1，整体结果上要加上二进制1产生的贡献
        }
        else 
        {
            th = th - w[son[u][!v]];
            u = son[u][v];
            res = 2 * res; //相同二进制异或得0，整体结果上要加上二进制0产生的贡献
        }
    }
    return res;
}

int main()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++) 
    {
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
    }

    for(int i = 0; i <= n; i++) add(s[i]);
    
    k = 2 * k; //由于s中两个数的最大异或值互为一致，所以找到2k个最大的，然后加起来除以2即可
    for(int i = 0; i <= n; i++) //把所有与s[i]异或值第一大的加入优先队列
    {
        ll val = find(s[i], 1);
        q.push({i, 1, val});
    }
    while(k--) //重复2k次，取前2k个最大的异或值
    {
        Node node = q.top();
        ans += node.val;
        q.pop();
        if(node.th < n)
        {
            node.th++;
            node.val = find(s[node.x], node.th);
            q.push(node);
        }   
    }
    
    cout << ans / 2;

    return 0;
}