Nikitosh 和异或 —— 一道 trie 树的题用可持久化 trie 水 然后翻车了...

时间:2022-03-18 20:40:23

题意简介

题目就是叫你找两个不重合的非空区间,使得这两个区间里的数异或后相加的和最大

(看到异或,没错就决定是你了可持久化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 水 然后翻车了...的更多相关文章

  1. 算法笔记--字典树(trie 树)&amp&semi;&amp&semi; ac自动机 &amp&semi;&amp&semi; 可持久化trie

    字典树 简介:字典树,又称单词查找树,Trie树,是一种树形结构,是哈希树的变种. 优点:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较. 性质:根节点不包含字符,除根节点外每一个 ...

  2. HDU 1251 Trie树模板题

    1.HDU 1251 统计难题  Trie树模板题,或者map 2.总结:用C++过了,G++就爆内存.. 题意:查找给定前缀的单词数量. #include<iostream> #incl ...

  3. Codeforces 633C Spy Syndrome 2 &vert; Trie树裸题

    Codeforces 633C Spy Syndrome 2 | Trie树裸题 一个由许多空格隔开的单词组成的字符串,进行了以下操作:把所有字符变成小写,把每个单词颠倒过来,然后去掉单词间的空格.已 ...

  4. poj3630 Phone List &lpar;trie树模板题&rpar;

    Phone List Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 26328   Accepted: 7938 Descr ...

  5. HDU 1251 统计难题 (Trie树模板题)

    题目链接:点击打开链接 Problem Description Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单 ...

  6. 利用trie树实现前缀输入提示及trie的python实现

    代码来自https://github.com/wklken/suggestion/blob/master/easymap/suggest.py 还实现了缓存功能,搜索某个前缀超过一定次数时,进行缓存, ...

  7. 835&period; 字符串统计(Trie树模板题)

    维护一个字符串集合,支持两种操作: “I x”向集合中插入一个字符串x: “Q x”询问一个字符串在集合中出现了多少次. 共有N个操作,输入的字符串总长度不超过 105105,字符串仅包含小写英文字母 ...

  8. hihocoder&lowbar;1014&colon; Trie树(Trie树模板题)

    题目链接 #include<bits/stdc++.h> using namespace std; ; struct T { int num; T* next[]; T() { num=; ...

  9. hihocoder 1014&colon; Trie树(Trie树模板题)

    题目链接 #include<bits/stdc++.h> using namespace std; ; struct T { int num; T* next[]; T() { num=; ...

随机推荐

  1. service mysql start出错,mysql启动不了,解决mysql&colon; unrecognized service错误

    service mysql start出错,mysql启动不了,解决mysql: unrecognized service错误的方法如下: [root@ctohome.com ~]# service ...

  2. Git &plus; BeyondCompare

    Mac 环境: 1. 安装 BeyondCompare 2. 配置 ~/.gitconfig [diff] tool = bcomp [merge] tool = bcomp [difftool &q ...

  3. 图算法(一)——基本图算法(BFS,DFS及其应用)(1)

    1)BFS 广度优先搜索:给定源节点s,生成广度优先搜索树广度优先搜索树中从节点s到节点v的简单路径对应的就是s到v的最短路径(边数最少的路径)广度优先:将已发现节点与未发现节点之间的边界(灰色节点) ...

  4. 火车车次查询-余票查询--Api接口

    1.来自12306的火车车次数据 使用12306网站的接口,查询余票.此接口采集自 这里. 全国火车站代号字典,下载 . 火车票余票查询 http://dynamic.12306.cn/otsquer ...

  5. 十大面试问题解惑,秒杀一切HR、技术面试

    最能体现求职者能力的就是面试,能不能拿到Offer,取决于你面试时的表现,只有有准备才能在面试过程中游刃有余.小编收集了10个面试官最爱提的问题,虽然题目千变万化,但是万变不离其宗,只要掌握了答题的技 ...

  6. Nginx的知识分享,继续上次的分享

    5. Nginx配置文件精讲二 #这里为后端服务器wugk应用集群配置,根据后端实际情况修改即可,tdt_wugk为负载均衡名称,可以任意指定 #但必须跟vhosts.conf虚拟主机的pass段一致 ...

  7. &lbrack;tornado&rsqb;websocket 最简单demo

    想法 前两天想看看django 长轮询或者是websocket的方案,发现都不太好使. tornado很适合做这个工作,于是找了些资料,参照了做了个最简单demo,以便备用. 具体的概念就不说了,to ...

  8. 分布式锁(一) Zookeeper分布式锁

    什么是Zookeeper? Zookeeper(业界简称zk)是一种提供配置管理.分布式协同以及命名的中心化服务,这些提供的功能都是分布式系统中非常底层且必不可少的基本功能,但是如果自己实现这些功能而 ...

  9. AppScan--图解Web扫描工具IBM Security App Scan Standard

    App Scan用法:   首先打开IBM Security AppScan Standard 工具   点击 创建新的扫描 ->  点击”常规扫描“ ->之后你就会看到如下图:     ...

  10. ev3&lowbar;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 ...