蓝桥杯真题 - 异或和之差 - 题解

题目链接：https://www.lanqiao.cn/problems/3524/learning/

个人评价：难度 3 星（满星：5）
前置知识：前缀和，字典树

---

整体思路

• 定义 $lmax[i]$ 为所有右端点小于等于 $i$ 的区间异或和的最大值，$rmax[i]$ 为所有左端点大于等于 $i$ 的区间异或和最大值，同理定义 $lmin[i]$ 与 $rmin[i]$，则答案如下：

$$ans=\max (lmax[i]-rmin[i+1],rmax[i+1]-lmin[i])i\in [2,n]$$

• 考虑 $lmax$ 数组的维护（$lmin,rmin,rmax$ 数组同理），在枚举到第 $i$ 个数字时，如果能快速找到以 $i$ 为右端点的所有区间异或和最大值，再将这个最大值与 $lmax[i-1]$ 取 $max$，就是 $lmax[i]$ 的值；
• 定义 $sum[i]$ 为前 $i$ 个数字的前缀异或和，将 $sum[i]$ 与所有 $sum[j](j\in [0,i))$ 异或和的最大值即第二点所求值，将所有 $sum[j]$ 放入 $01$ 字典树中，即可 $O(\log n)$ 时间复杂度求出该最大值。

过题代码

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

typedef long long LL;
const int maxn = 200000 + 100;
const int maxcnt = 200000 * 21 + 100;
const int Size = 2;

// 01 Trie 模板代码
struct Trie {
    int root, cnt;
    int tree[maxcnt][Size];

    int create() {
        ++cnt;
        memset(tree[cnt], 0, sizeof(tree[cnt]));
        return cnt;
    }

    void Init() {
        cnt = 0;
        root = create();
    }

    void add(int x) {
        int pos = root;
        for(int i = 20; i >= 0; --i) {
            int w = ((x >> i) & 1);
            if(tree[pos][w] == 0) {
                tree[pos][w] = create();
            }
            pos = tree[pos][w];
        }
    }

    // 从字典树中找到与 x 异或的最大值的结果
    int queryMax(int x) {
        int pos = root;
        int ret = 0;
        for(int i = 20; i >= 0; --i) {
            int w = ((x >> i) & 1);
            if(tree[pos][w ^ 1] == 0) {
                pos = tree[pos][w];
            } else {
                pos = tree[pos][w ^ 1];
                ret ^= (1 << i);
            }
        }
        return ret;
    }

    // 从字典树中找到与 x 异或的最小值的结果
    int queryMin(int x) {
        int pos = root;
        int ret = 0;
        for(int i = 20; i >= 0; --i) {
            int w = ((x >> i) & 1);
            if(tree[pos][w] == 0) {
                pos = tree[pos][w ^ 1];
                ret ^= (1 << i);
            } else {
                pos = tree[pos][w];
            }
        }
        return ret;
    }
} trie;

int n, ans, sum;
int num[maxn];
int lmax[maxn], rmax[maxn], lmin[maxn], rmin[maxn];

int main() {
#ifdef ExRoc
    freopen("test.txt", "r", stdin);
#endif // ExRoc
    ios::sync_with_stdio(false);

    cin >> n;

    trie.Init();
    // 前缀和必须将第 0 位放入
    sum = 0;
    trie.add(sum);
    for (int i = 1; i <= n; ++i) {
        cin >> num[i];
        sum ^= num[i];
        lmax[i] = trie.queryMax(sum);
        lmin[i] = trie.queryMin(sum);
        trie.add(sum);
    }

    trie.Init();
    sum = 0;
    trie.add(sum);
    for (int i = n; i >= 1; --i) {
        sum ^= num[i];
        rmax[i] = trie.queryMax(sum);
        rmin[i] = trie.queryMin(sum);
        trie.add(sum);
    }

    // 最后做一遍前缀 / 后缀 max / min
    for (int i = 2; i <= n; ++i) {
        lmax[i] = max(lmax[i], lmax[i - 1]);
        lmin[i] = min(lmin[i], lmin[i - 1]);
        rmax[n - i + 1] = max(rmax[n - i + 1], rmax[n - i + 2]);
        rmin[n - i + 1] = min(rmin[n - i + 1], rmin[n - i + 2]);
    }

    for (int i = 1; i < n; ++i) {
        ans = max({ans, lmax[i] - rmin[i + 1], rmax[i + 1] - lmin[i]});
    }
    cout << ans << endl;

    return 0;
}

原文地址：https://blog.csdn.net/CSDNjiangshan/article/details/145250187

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！