雄安免费网站建设,wordpress做h5,技校计算机专业主要学什么,石家庄专业模板网站制作价格Powered by:NEFU AB-IN
Link 文章目录3485. 最大异或和题意思路代码3485. 最大异或和 题意 给定一个非负整数数列 a#xff0c;初始长度为 N。 请在所有长度不超过 M的连续子数组中#xff0c;找出子数组异或和的最大值。 子数组的异或和即为子数组中所有元素按位异或得到的…Powered by:NEFU AB-IN
Link 文章目录3485. 最大异或和题意思路代码3485. 最大异或和 题意 给定一个非负整数数列 a初始长度为 N。 请在所有长度不超过 M的连续子数组中找出子数组异或和的最大值。 子数组的异或和即为子数组中所有元素按位异或得到的结果。 注意子数组可以为空。 思路 可持久化Trie 非递归模板 个人认为是最通俗易懂、和简洁的版本 代码讲解 Link 首先说一下思路在前缀异或和数组中就是在每个数的前m-1区间内找异或的最大值 简要介绍一下各个数组和变量的含义 ver 其实就是version的意思代表这个结点id是属于哪个版本的树 下标是结点id值是树的id其实本题中也和原数组a的id对应 root 比如root[i] 1代表第i颗树的根节点id为1 下标是树的id值是结点id 比如 1 2 3 4 5 这五个数为下标以5为例查询的时候便是query(root[4], 3, a[5]) 为什么是3呢 因为是前缀异或和数组l需要减一其次需要注意这个值必须大于等于0就是在查询的时候和0取一个最大值 为什么是root[4] 其实root[5]也可以因为5这个下标的值不可能取毕竟自己异或自己为0能省一步是一步 代码 /*
* Author: NEFU AB-IN
* Date: 2023-02-27 09:36:13
* FilePath: \Acwing\3485\3485.cpp
* LastEditTime: 2023-02-27 20:03:43
*/
#include bits/stdc.h
using namespace std;
#define int long long
#undef int#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS \ios::sync_with_stdio(false); \cin.tie(nullptr); \cout.tie(nullptr)
#define DEBUG(X) cout #X : X \n
typedef pairint, int PII;const int N 1e5 10, M N * 32, INF 0x3f3f3f3f;int ver[M], root[N], son[M][2], idx;
int n, m;
int a[N];void insert(int x, int y, int k)
// x为当前树的根节点编号y为上一个树的根节点编号k为第几棵树
{ver[x] k;for (int i 30; i 0; --i){int u a[k] i 1;son[x][!u] son[y][!u];son[x][u] idx;x son[x][u];y son[y][u];ver[x] k;}
}int query(int x, int L, int v)
// x为当前树的根节点L为不能超越的树编号左边界v为输入函数的定值
{for (int i 30; i 0; --i){int u v i 1;if (ver[son[x][!u]] L)x son[x][!u]; // res 1 i;elsex son[x][u];}return a[ver[x]] ^ v;
}signed main()
{IOS;cin n m;// initroot[0] idx;ver[0] -1;insert(root[0], 0, 0);for (int i 1; i n; i){cin a[i];a[i] ^ a[i - 1];root[i] idx;insert(root[i], root[i - 1], i);}int res 0;for (int i 1; i n; i){res max(res, query(root[i], max(0, i - m), a[i]));}cout res \n;return 0;
}
