BZOJ 4260 Codechef REBXOR 01trie
2024-08-30 22:15:11
好题。。。开阔思路
把每个前缀异或和依次插入$01trie$,插之前找一个最优的(就是从高位向低位贪心,尽量走相反方向)看看能不能更新答案,此时相当于找到了区间右端点不超过某个点$r$的最大或和$f[r]$。对于后缀也同理来一波上面的操作,然后就找到了区间左端点端点不少于某个点$l$的最大异或和。所以答案就是$max(f[某个位置]+query(下个位置开始的后缀))$。
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define ll long long
#define R register int
using namespace std;
namespace Fread {
static char B[<<],*S=B,*D=B;
#define getchar() (S==D&&(D=(S=B)+fread(B,1,1<<15,stdin),S==D)?EOF:*S++)
inline int g() {
R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=ret*+(ch^); while(isdigit(ch=getchar())); return ret*fix;
} inline bool isempty(const char& ch) {return ch<=||ch>=;}
inline void gs(char* s) {register char ch; while(isempty(ch=getchar())); do *s++=ch; while(!isempty(ch=getchar()));}
}using Fread::g; using Fread::gs;
const int N=;
int t[N*][],tot,n,a[N],s[N],b[N],f[N],ans;
inline void ins(int x) { R now=;
for(R i=;~i;--i) {
R ch=(x>>i)&;
if(!t[now][ch]) t[now][ch]=++tot;
now=t[now][ch];
}
}
inline int query(int x) { R now=,ret=;
for(R i=;~i;--i) {
R ch=(x>>i)&;
if(!t[now][ch^]) now=t[now][ch^];
else now=t[now][ch^],ret+=(<<i);
} return ret;
}
signed main() {
#ifdef JACK
freopen("NOIPAK++.in","r",stdin);
#endif
n=g(); for(R i=;i<=n;++i) a[i]=g();
for(R i=;i<=n;++i) s[i]=s[i-]^a[i];
for(R i=n;i;--i) b[i]=b[i+]^a[i]; ins();
for(R i=;i<=n;++i) f[i]=max(f[i-],query(s[i])),ins(s[i]);
memset(t,,sizeof(t)); tot=; ins();
for(R i=n;i;--i) ans=max(ans,f[i-]+query(b[i])),ins(b[i]);
printf("%d\n",ans);
}
2019.06.13
最新文章
- 以最简单方式学习Linux
- java16
- Javascript刷新页面的几种方法
- 修改linux运行级别
- win安装mysql5.1
- Problem 1007 幸运数 线段树成段更新
- Python通过Manager方式实现多个无关联进程共享数据
- mysql 引擎区分
- Unity 制作RPG小地图
- ABAP字符串操作 截取字符长度 取位数
- Hibernate 系列教程1-枚举单例类
- 关于spingMVC使用时配置自动扫描出现的路径报错
- yum方式安装kubernetes
- STM32的USART应用问题(不定时添加)
- 前端SEO与爬虫与SSR(Server Side Render)
- H5 字符实体
- Hibernate学习(四)———— 双向多对多映射关系
- js基础-基本包装类型
- mysql 字符串转数据丢失精度,mysql转换丢失精度,mysql CAST 丢失精度
- CCF 100012. 技能树
热门文章
- Gym - 100570B :ShortestPath Query(SPFA及其优化)
- POJ3080 POJ3450Corporate Identity(广义后缀自动机||后缀数组||KMP)
- JS字符串类型转日期然后进行日期比较
- Poj 1860 Currency Exchange(Bellman-Ford,SPFA解单源最短路径问题)
- 问题13:如何在for语句中迭代多个可迭代的对象
- Unity堆内存优化
- 11、perl语言的记录分割符$/ $\
- p2590&;bzoj1036 树的统计
- JavaEE资源
- doxygen+ graphviz 开源工具生成源码调用树的wiki