bzoj 4260: REBXOR Trie+乱搞
2024-09-02 10:43:33
题目大意:
题解:
啊啊啊.
被这种SB题坑了半天.
求出异或前缀和后
从n到1枚举\(r_1\)的取值就好了啊.
用Trie 算出1 ~ \(r_1-1\)和\(a_{r_1}\)的异或最大值ans1
以及\(a_{r_1 + 1}\)和\(r_1 + 1\) ~ n的异或最大值ans2
用ans1 + max{ans2}更新答案就好了
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
inline void read(int &x){
x=0;char ch;bool flag = false;
while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true;
while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;
}
const int maxn = 600010;
struct Node{
Node* ch[2];
int siz;
}*null,*root[maxn];
Node mem[maxn*32],*it;
inline void init(){
it = mem;
null = it++;null->ch[0] = null->ch[1] = null;
null->siz = 0;
}
Node* insert(Node *rt,int x,int d){
Node *p = it++;*p = *rt;p->siz ++;
if(d == -1) return p;
int id = (x>>d)&1;
p->ch[id] = insert(p->ch[id],x,d-1);
return p;
}
int query(Node *p1,Node *p2,int x,int d){
if(d == -1) return 0;
int id = (x>>d)&1;
if(p2->ch[id^1]->siz - p1->ch[id^1]->siz > 0)
return (1<<d) | query(p1->ch[id^1],p2->ch[id^1],x,d-1);
return query(p1->ch[id],p2->ch[id],x,d-1);
}
void dfs(Node *p){
printf("siz = %d\n",p->siz);
if(p->ch[0] != null){puts("-> ch[0] : ");dfs(p->ch[0]);}
if(p->ch[1] != null){puts("-> ch[1] : ");dfs(p->ch[1]);}
puts("return");
}
int a[maxn];
int main(){
int n;read(n);init();root[0] = null;
root[1] = insert(root[0],0,31);
++n;
for(int i=2;i<=n;++i){
read(a[i]);a[i] ^= a[i-1];
root[i] = insert(root[i-1],a[i],31);
}
int ans = 0,max2 = 0;
for(int i=n;i>=2;--i){
max2 = max(max2,query(root[i],root[n],a[i],31));
ans = max(ans,max2 + query(root[0],root[i],a[i],31));
}printf("%d\n",ans);
getchar();getchar();
return 0;
}
最新文章
- 【BZOJ 1005】【HNOI 2008】明明的烦恼
- C# 定时器 Timers.Timer Forms.Timer
- Synchronized和Static Synchronized区别
- angularJs , json,html片段,bootstrap timepicker angular
- TCP/IP包格式详解
- C语言 负数取余的原理
- Myeclipse多行注释快捷键及其他快捷键
- WebApi(四)-Post接口请求失败或接受不到参数(解决方法)
- 奇葩问题:spring+mybaits项目突然出现其中一些Mapper类找不到
- Android分屏显示LogCat
- SAP HANA中创建计算视图(Calculation View)
- mysql 常用技巧
- [转]django-registration quickstart
- linux 乌班图 xshell链接不上服务器
- java - Integer、int 、String相互转换总结
- windwos 下编译minicap
- java面试——jvm
- Shell逻辑语句
- STM32 printf()函数和scanf()函数重定向到串口
- 2018-2019-2 网络对抗技术 20165230 Exp5 MSF基础应用
热门文章
- 2016/05/17 thinkphp3.2.2 分页的使用:①在Home下设置Publics文件夹或在thinkPHP下library的vender 把page.class.php 考贝进入 ②通过new 实例化方式调用 $page=new \Home\Publics\Page($total,3);
- spring struts2整合
- python cookbook第三版学习笔记十七:委托属性
- vim 光标的移动和跳转文件的位置
- LeetCode:乘法表中的第K小的数【668】
- gulp 打包报错:ReferenceError: internalBinding is not defined
- 扣出thinkphp数据库操作类
- POJ - 2195 Going Home 【KM】
- Executor中的类
- Data Structure Array: Find the minimum distance between two numbers