2023.2.28AcWing蓝桥杯集训·每日一题

今日复习的知识点为Tire树(字典树)。字典树可用于快速存储和查找字符串，并且 \(0-1\) 字典树也可以用于解决异或问题。

AcWing3485.最大异或和

题目描述

给定一个非负整数数列 \(a\)，初始长度为 \(N\)。

请在所有长度不超过 \(M\) 的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

输入格式

第一行包含两个整数 \(N,M\)。

第二行包含 \(N\) 个整数，其中第 \(i\) 个为 \(a_i\)。

输出格式

输出可以得到的子数组异或和的最大值。

数据范围

对于 \(20\%\) 的数据，\(1≤M≤N≤100\)
对于 \(50\%\) 的数据，\(1≤M≤N≤1000\)
对于 \(100\%\) 的数据，\(1≤M≤N≤10^5,0≤a_i≤2^{31}−1\)

输入样例

3 2
1 2 4

输出样例

6

解题思路

此题目我们采用字典树。首先我们要计算的是区间异或和的最大值，那么提到区间，那么我们应该想到前缀和，那么此题目，我们可以预处理前缀异或和，那么对于区间 \([l,r]\) 的区间异或和为 \(a_l\bigoplus a_{l+1}\bigoplus a_{l+2}...\bigoplus a_r=s[r]\bigoplus s[l-1]\)，这里是利用的异或运算的自反性。这样的话我们就相当于将问题转换为在不大于 \(m\) 的区间长度内，获得该区间的某两个前缀异或和的异或的最大值。我们动态的维护一个区间长度为 \(m\) 的数组构成的 \(0-1\) 字典树。

C++代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100010, M = 3100010;

int n, m;
int s[N], son[M][2], cnt[M], idx;

void insert(int x, int v) // v表示以某节点为根的子树的数量
{
    int p = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += v;
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if (cnt[son[p][!u]]) 
        {
            res += 1 << i;
            p = son[p][!u];
        }
        else p = son[p][u];
    }
    return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++) 
    {
        int x;
        scanf("%d", &x);
        s[i] = s[i - 1] ^ x;
    }
    int res = 0;
    insert(s[0], 1);
    for (int i = 1; i <= n; i ++)
    {
        if (i > m) insert(s[i - m - 1], -1);
        insert(s[i], 1);
        res = max(res, query(s[i]));
    }
    printf("%d", res);
    return 0;
}