思路同第一篇题解,样例模拟无误,WA 5 分求助
查看原帖
思路同第一篇题解,样例模拟无误,WA 5 分求助
932039
lzy20091001楼主2024/3/3 12:46
#include <iostream>
#include <queue>

#define int long long

struct Node // 堆中的元素
{
    int val; // 异或和
    int x, y;
    friend bool operator<(Node u, Node v)
    {
        return u.val < v.val;
    }
};

int trieSize;                                    // trie 大小
int a[500005], trie[16000005][2], cnt[16000005]; // a 为异或前缀和, cnt 为 trie 的子树大小
Node d[500005];                                  // 异或和

std::priority_queue<Node> pq;

void insert(int val) // trie 插入元素
{
    int u = 0;
    for (int i = (1ll << 3); i >= 1ll; i >>= 1ll)
    {
        bool t = val & i;
        if (trie[u][t] == 0)
            trie[u][t] = ++trieSize;
        u = trie[u][t];
        cnt[u]++;
    }
}

int query(int val, int k) // 查询 val 的第 k 大的配对异或和
{
    // std::cout << val << " " << k << "\n";
    int res = 0;
    int u = 0;
    for (int i = (1ll << 3); i >= 1ll; i >>= 1ll)
    {
        bool t = val & i;
        if (trie[u][!t] == 0)
            u = trie[u][t];
        else if (cnt[trie[u][!t]] >= k) // 贪心决定走哪边
        {
            u = trie[u][!t];
            res += i;
        }
        else
        {
            u = trie[u][t];
            k -= cnt[trie[u][!t]];
        }
        // std::cout << u << " " << k << "\n";
    }
    // std::cout << res << "\n\n";
    return res;
}

main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    int n, k;
    long long ans = 0;

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

    for (int i = 0; i <= n; i++)
        insert(a[i]);
    for (int i = 0; i <= n; i++)
    {
        d[i].val = query(a[i], 1ll);
        d[i].x = i;
        d[i].y = 1ll;
        pq.push(d[i]);
    }

    for (int i = 1ll; i <= 2 * k; i++)
    {
        Node t = pq.top();
        pq.pop();
        ans += t.val;
        if (t.y < n)
            pq.push({query(a[t.x], t.y + 1), t.x, t.y + 1});
    }

    std::cout << ans / 2 << "\n";

    return 0;
}
2024/3/3 12:46
加载中...