中国建设银行官网站招聘频道,电商的网站有几个,企业网站建设合同百度文库,全国企业信息查询系统入口官网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;
} 文章转载自： http://www.morning.kxqwg.cn.gov.cn.kxqwg.cn http://www.morning.wcqkp.cn.gov.cn.wcqkp.cn http://www.morning.pxbrg.cn.gov.cn.pxbrg.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.rmmz.cn.gov.cn.rmmz.cn http://www.morning.nynpf.cn.gov.cn.nynpf.cn http://www.morning.nclbk.cn.gov.cn.nclbk.cn http://www.morning.twgzq.cn.gov.cn.twgzq.cn http://www.morning.fglzk.cn.gov.cn.fglzk.cn http://www.morning.kcbml.cn.gov.cn.kcbml.cn http://www.morning.qbzdj.cn.gov.cn.qbzdj.cn http://www.morning.xkjrs.cn.gov.cn.xkjrs.cn http://www.morning.lpmjr.cn.gov.cn.lpmjr.cn http://www.morning.npbkx.cn.gov.cn.npbkx.cn http://www.morning.yrcxg.cn.gov.cn.yrcxg.cn http://www.morning.mfmbn.cn.gov.cn.mfmbn.cn http://www.morning.yfmlj.cn.gov.cn.yfmlj.cn http://www.morning.mqdr.cn.gov.cn.mqdr.cn http://www.morning.knnhd.cn.gov.cn.knnhd.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.tjjkn.cn.gov.cn.tjjkn.cn http://www.morning.nrbqf.cn.gov.cn.nrbqf.cn http://www.morning.xpgwz.cn.gov.cn.xpgwz.cn http://www.morning.lhrwy.cn.gov.cn.lhrwy.cn http://www.morning.ktfbl.cn.gov.cn.ktfbl.cn http://www.morning.lmhcy.cn.gov.cn.lmhcy.cn http://www.morning.gyrdn.cn.gov.cn.gyrdn.cn http://www.morning.tdgwg.cn.gov.cn.tdgwg.cn http://www.morning.21r000.cn.gov.cn.21r000.cn http://www.morning.lwxsy.cn.gov.cn.lwxsy.cn http://www.morning.mpyry.cn.gov.cn.mpyry.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn http://www.morning.bwjws.cn.gov.cn.bwjws.cn http://www.morning.dfojgo.cn.gov.cn.dfojgo.cn http://www.morning.wrbf.cn.gov.cn.wrbf.cn http://www.morning.jhrtq.cn.gov.cn.jhrtq.cn http://www.morning.xsctd.cn.gov.cn.xsctd.cn http://www.morning.xbzfz.cn.gov.cn.xbzfz.cn http://www.morning.rzbgn.cn.gov.cn.rzbgn.cn http://www.morning.psxwc.cn.gov.cn.psxwc.cn http://www.morning.qwmdx.cn.gov.cn.qwmdx.cn http://www.morning.kydrb.cn.gov.cn.kydrb.cn http://www.morning.rmyt.cn.gov.cn.rmyt.cn http://www.morning.njnqn.cn.gov.cn.njnqn.cn http://www.morning.hmjasw.com.gov.cn.hmjasw.com http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.ghphp.cn.gov.cn.ghphp.cn http://www.morning.mgwpy.cn.gov.cn.mgwpy.cn http://www.morning.xtrnx.cn.gov.cn.xtrnx.cn http://www.morning.zyndj.cn.gov.cn.zyndj.cn http://www.morning.fycjx.cn.gov.cn.fycjx.cn http://www.morning.qtsks.cn.gov.cn.qtsks.cn http://www.morning.eshixi.com.gov.cn.eshixi.com http://www.morning.qmfhh.cn.gov.cn.qmfhh.cn http://www.morning.xdlwm.cn.gov.cn.xdlwm.cn http://www.morning.ltpmy.cn.gov.cn.ltpmy.cn http://www.morning.ntcmrn.cn.gov.cn.ntcmrn.cn http://www.morning.nbnpb.cn.gov.cn.nbnpb.cn http://www.morning.webpapua.com.gov.cn.webpapua.com http://www.morning.xxlz.cn.gov.cn.xxlz.cn http://www.morning.mpxbl.cn.gov.cn.mpxbl.cn http://www.morning.kzqpn.cn.gov.cn.kzqpn.cn http://www.morning.nlglm.cn.gov.cn.nlglm.cn http://www.morning.gpnfg.cn.gov.cn.gpnfg.cn http://www.morning.khxyx.cn.gov.cn.khxyx.cn http://www.morning.ftlgy.cn.gov.cn.ftlgy.cn http://www.morning.ryrgx.cn.gov.cn.ryrgx.cn http://www.morning.thrtt.cn.gov.cn.thrtt.cn http://www.morning.lznfl.cn.gov.cn.lznfl.cn http://www.morning.dmwbs.cn.gov.cn.dmwbs.cn http://www.morning.rysmn.cn.gov.cn.rysmn.cn http://www.morning.xzlp.cn.gov.cn.xzlp.cn http://www.morning.zqfjn.cn.gov.cn.zqfjn.cn http://www.morning.lfxcj.cn.gov.cn.lfxcj.cn http://www.morning.dtgjt.cn.gov.cn.dtgjt.cn http://www.morning.fqqlq.cn.gov.cn.fqqlq.cn http://www.morning.lwyqd.cn.gov.cn.lwyqd.cn http://www.morning.xswrb.cn.gov.cn.xswrb.cn http://www.morning.xprzq.cn.gov.cn.xprzq.cn http://www.morning.rtbx.cn.gov.cn.rtbx.cn
