bzoj2134: 单选错位(trie)
2024-10-14 04:58:10
预处理前后缀异或和,用trie得到前后缀最大答案,枚举中间点把左右两边加起来就是当前中间点的最大答案了...这个操作没见过,比较有意思,记录一下
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
const int maxn=, inf=1e9;
struct poi{int nxt[];}tree[maxn*];
int n, ans, tott;
int a[maxn], suml[maxn], sumr[maxn], ansl[maxn], ansr[maxn];
inline void read(int &k)
{
int f=; k=; char c=getchar();
while(c<'' || c>'') c=='-'&&(f=-), c=getchar();
while(c<='' && c>='') k=k*+c-'', c=getchar();
k*=f;
}
inline int getans(int x)
{
int ans=, now=;
for(int i=, y;~i;i--)
if(tree[now].nxt[(y=(x&(<<i))!=)^])
ans+=(<<i), now=tree[now].nxt[y^];
else now=tree[now].nxt[y];
return ans;
}
inline void insert(int x)
{
int now=;
for(int i=, y;~i;i--)
if(tree[now].nxt[y=(x&(<<i))!=]) now=tree[now].nxt[y];
else tree[now].nxt[y]=++tott, now=tott;
}
int main()
{
read(n);
for(int i=;i<=n;i++) read(a[i]), suml[i]=suml[i-]^a[i];
for(int i=n;i;i--) sumr[i]=sumr[i+]^a[i];
insert();
for(int i=;i<=n;i++) ansl[i]=max(ansl[i-], getans(suml[i])), insert(suml[i]);
memset(tree, , sizeof(tree)); insert();
for(int i=n;i;i--) ansr[i]=max(ansr[i+], getans(sumr[i])), insert(sumr[i]);
for(int i=;i<=n;i++) ans=max(ans, ansl[i]+ansr[i]);
printf("%d\n", ans);
}
最新文章
- 智软科技医疗器械GSP监管软件通过多省市药监局检查
- WPF打印、预览、导出PDF
- SQL语句性能测试
- hdu 1166
- LibSVM使用指南
- UVA 10537 The Toll! Revisited uva1027 Toll(最短路+数学坑)
- Android studio gradle配置
- Delphi中获取Unix时间戳及注意事项(c语言中time()是按格林威治时间计算的,比北京时间多了8小时)
- JVM-Java程序性能监控-初级篇
- 一个请求中,ADF、JSF究竟做了哪些工作
- SpringMVC 配置
- Postman----设置代理抓取手机上的请求
- [开发技巧]&#183;TensorFlow中numpy与tensor数据相互转化
- Android NDK开发调试
- 【转】这五种方法前四种方法只支持IE浏览器,最后一个方法支持当前主流的浏览器(火狐,IE,Chrome,Opera,Safari)
- Intel x86_64 Architecture Background 3
- js实现的map方法
- RN导航栏使用
- View 的滑动
- 关于jQuery Form Plugin使用心得
热门文章
- 20155217《网络对抗》Exp03 免杀原理与实践
- 2017-2018-2 20155224『网络对抗技术』Exp6:信息搜集与漏洞扫描
- 20155226 Exp2 后门原理与实践
- 20155306 白皎 免考实践总结——0day漏洞
- Python基础(字符串和编码)
- mfc CString,string,char* 之间的转换
- [Deep-Learning-with-Python]基于Keras的房价预测
- web项目_学生证管理系统
- .Net Core 分布式微服务框架 - Jimu 添加 Swagger 支持
- linux之 sed 基础