好题。。。开阔思路


把每个前缀异或和依次插入$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

最新文章

  1. 以最简单方式学习Linux
  2. java16
  3. Javascript刷新页面的几种方法
  4. 修改linux运行级别
  5. win安装mysql5.1
  6. Problem 1007 幸运数 线段树成段更新
  7. Python通过Manager方式实现多个无关联进程共享数据
  8. mysql 引擎区分
  9. Unity 制作RPG小地图
  10. ABAP字符串操作 截取字符长度 取位数
  11. Hibernate 系列教程1-枚举单例类
  12. 关于spingMVC使用时配置自动扫描出现的路径报错
  13. yum方式安装kubernetes
  14. STM32的USART应用问题(不定时添加)
  15. 前端SEO与爬虫与SSR(Server Side Render)
  16. H5 字符实体
  17. Hibernate学习(四)———— 双向多对多映射关系
  18. js基础-基本包装类型
  19. mysql 字符串转数据丢失精度,mysql转换丢失精度,mysql CAST 丢失精度
  20. CCF 100012. 技能树

热门文章

  1. Gym - 100570B :ShortestPath Query(SPFA及其优化)
  2. POJ3080 POJ3450Corporate Identity(广义后缀自动机||后缀数组||KMP)
  3. JS字符串类型转日期然后进行日期比较
  4. Poj 1860 Currency Exchange(Bellman-Ford,SPFA解单源最短路径问题)
  5. 问题13:如何在for语句中迭代多个可迭代的对象
  6. Unity堆内存优化
  7. 11、perl语言的记录分割符$/ $\
  8. p2590&amp;bzoj1036 树的统计
  9. JavaEE资源
  10. doxygen+ graphviz 开源工具生成源码调用树的wiki