题意简介
题目就是叫你找两个不重合的非空区间,使得这两个区间里的数异或后相加的和最大
(看到异或,没错就决定是你了可持久化trie!)
思路
水一波字典树,莫名觉得这题可持久化能过,于是水了一发挂了,造了一波数据,然后发现是自己在做完一遍可持久化之后cnt 没有清零....
其实要用可持久化trie 来做的话也就是常规操作(话说普通字典树不也是常规操作?)
也就是前缀和往可持久化trie 上update , 然后每个 L[i]、R[i] 记录当前点为右(左)区间的最大区间异或和
然后就是枚举断点了,考虑我们枚举到的断点前的那个区间其实是确定的(异或和最大的那个),
那么我们拿当前断点作为第二个 区间的左端点,前面的区间由 lef 变量不断更新,最后就能累加出答案。
于是没什么好说的了,板子题。
代码如下
//by Judge
#include<iostream>
#include<cstdio>
using namespace std;
const int M=4e5+;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[<<],*p1=buf,*p2=buf;
inline int read(){
int x=,f=; char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-;
for(;isdigit(c);c=getchar()) x=x*+c-''; return x*f;
}
int n,cnt,a[M],L[M],R[M];
int d[],rt[M<<],son[M<<][],sum[M<<];
inline void split(int k){ //换二进制
int i,len=;
while(k) d[++len]=k&,k>>=;
for(int i=len+;i<=;++i) d[i]=;
}
inline void update(int& now,int las){ //可持久化的更新
sum[now=++cnt]=sum[las]+;
int i,tmp=now;
for(i=;i;--i){
son[tmp][d[i]^]=son[las][d[i]^],
son[tmp][d[i]]=++cnt,las=son[las][d[i]],
sum[tmp=cnt]=sum[las]+;
}
}
inline int query(int u,int v){ //询问区间内与当前数的最大异或和
int ans=,i;
for(i=;i;--i){
if(sum[son[v][d[i]^]]-sum[son[u][d[i]^]]>)
ans|=(<<i-),u=son[u][d[i]^],v=son[v][d[i]^];
else u=son[u][d[i]],v=son[v][d[i]];
} return ans;
}
int main(){ //分函数都是常规操作(因为我都是直接搞了自己的板子)
int x,lef,res=;
n=read(),++n;
split(),update(rt[],rt[]);
for(int i=;i<=n;++i)
a[i]=read();
for(int i=,sum=;i<=n;++i){
split(sum^=a[i]),
update(rt[i],rt[i-]),
L[i]=query(rt[],rt[i]);
}
cnt=,split(),update(rt[],rt[]); //清零,从后往前再来一遍
for(int i=n,sum=;i>=;--i){
split(sum^=a[i]);
update(rt[n-i+],rt[n-i+]),
R[i]=query(rt[],rt[n-i+]);
} lef=L[];
for(int i=;i<=n;++i){ //从左到右处理答案
res=max(res,lef+R[i]),
lef=max(lef,L[i]);
} printf("%d\n",res); return ;
}
Nikitosh 和异或 —— 一道 trie 树的题用可持久化 trie 水 然后翻车了...的更多相关文章
-
算法笔记--字典树(trie 树)&;&; ac自动机 &;&; 可持久化trie
字典树 简介:字典树,又称单词查找树,Trie树,是一种树形结构,是哈希树的变种. 优点:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较. 性质:根节点不包含字符,除根节点外每一个 ...
-
HDU 1251 Trie树模板题
1.HDU 1251 统计难题 Trie树模板题,或者map 2.总结:用C++过了,G++就爆内存.. 题意:查找给定前缀的单词数量. #include<iostream> #incl ...
-
Codeforces 633C Spy Syndrome 2 | Trie树裸题
Codeforces 633C Spy Syndrome 2 | Trie树裸题 一个由许多空格隔开的单词组成的字符串,进行了以下操作:把所有字符变成小写,把每个单词颠倒过来,然后去掉单词间的空格.已 ...
-
poj3630 Phone List (trie树模板题)
Phone List Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 26328 Accepted: 7938 Descr ...
-
HDU 1251 统计难题 (Trie树模板题)
题目链接:点击打开链接 Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单 ...
-
利用trie树实现前缀输入提示及trie的python实现
代码来自https://github.com/wklken/suggestion/blob/master/easymap/suggest.py 还实现了缓存功能,搜索某个前缀超过一定次数时,进行缓存, ...
-
835. 字符串统计(Trie树模板题)
维护一个字符串集合,支持两种操作: “I x”向集合中插入一个字符串x: “Q x”询问一个字符串在集合中出现了多少次. 共有N个操作,输入的字符串总长度不超过 105105,字符串仅包含小写英文字母 ...
-
hihocoder_1014: Trie树(Trie树模板题)
题目链接 #include<bits/stdc++.h> using namespace std; ; struct T { int num; T* next[]; T() { num=; ...
-
hihocoder 1014: Trie树(Trie树模板题)
题目链接 #include<bits/stdc++.h> using namespace std; ; struct T { int num; T* next[]; T() { num=; ...
随机推荐
-
service mysql start出错,mysql启动不了,解决mysql: unrecognized service错误
service mysql start出错,mysql启动不了,解决mysql: unrecognized service错误的方法如下: [root@ctohome.com ~]# service ...
-
Git + BeyondCompare
Mac 环境: 1. 安装 BeyondCompare 2. 配置 ~/.gitconfig [diff] tool = bcomp [merge] tool = bcomp [difftool &q ...
-
图算法(一)——基本图算法(BFS,DFS及其应用)(1)
1)BFS 广度优先搜索:给定源节点s,生成广度优先搜索树广度优先搜索树中从节点s到节点v的简单路径对应的就是s到v的最短路径(边数最少的路径)广度优先:将已发现节点与未发现节点之间的边界(灰色节点) ...
-
火车车次查询-余票查询--Api接口
1.来自12306的火车车次数据 使用12306网站的接口,查询余票.此接口采集自 这里. 全国火车站代号字典,下载 . 火车票余票查询 http://dynamic.12306.cn/otsquer ...
-
十大面试问题解惑,秒杀一切HR、技术面试
最能体现求职者能力的就是面试,能不能拿到Offer,取决于你面试时的表现,只有有准备才能在面试过程中游刃有余.小编收集了10个面试官最爱提的问题,虽然题目千变万化,但是万变不离其宗,只要掌握了答题的技 ...
-
Nginx的知识分享,继续上次的分享
5. Nginx配置文件精讲二 #这里为后端服务器wugk应用集群配置,根据后端实际情况修改即可,tdt_wugk为负载均衡名称,可以任意指定 #但必须跟vhosts.conf虚拟主机的pass段一致 ...
-
[tornado]websocket 最简单demo
想法 前两天想看看django 长轮询或者是websocket的方案,发现都不太好使. tornado很适合做这个工作,于是找了些资料,参照了做了个最简单demo,以便备用. 具体的概念就不说了,to ...
-
分布式锁(一) Zookeeper分布式锁
什么是Zookeeper? Zookeeper(业界简称zk)是一种提供配置管理.分布式协同以及命名的中心化服务,这些提供的功能都是分布式系统中非常底层且必不可少的基本功能,但是如果自己实现这些功能而 ...
-
AppScan--图解Web扫描工具IBM Security App Scan Standard
App Scan用法: 首先打开IBM Security AppScan Standard 工具 点击 创建新的扫描 -> 点击”常规扫描“ ->之后你就会看到如下图: ...
-
ev3_basic——HITCON CTF 2018
[MISC] EN-US This challenge provides a jpg file and a pklg file. The jpg is shown a part of string o ...