BZOJ4260: Codechef REBXOR (01Tire树)

题意

题目链接

Sol

首先维护出前缀xor和后缀xor

对每个位置的元素插入到Trie树里面,每次找到和该前缀xor起来最大的元素

正反各做一遍,取最大。

记得要开log倍空间qwq。。

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-')f =- 1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, a[MAXN], s[MAXN], pmx[MAXN], smx[MAXN], ch[MAXN][2], tot;
void insert(int x) {
    int now = 0;
    for(int i = 0; i <= 30; i++) {
        int nxt = (x >> i & 1);
        if(!ch[now][nxt]) ch[now][nxt] = ++tot;
        now = ch[now][nxt];
    }
}
int Query(int x) {
    int now = 0, ans = 0;
    for(int i = 0; i <= 30; i++) {
        int nxt = (x >> i & 1);
        if(ch[now][nxt ^ 1]) ans += 1 << i, now = ch[now][nxt ^ 1];
        else now = ch[now][nxt];
    }
    return ans;
}
void solve(int *s, int *mx) {
    for(int i = 1; i <= N; i++) {
        s[i] = s[i - 1] ^ a[i];
        insert(s[i]);
        mx[i] = Query(s[i]);
        mx[i] = max(mx[i - 1], mx[i]);
    }
}
int main() {
    //freopen("3.in", "r", stdin); 
    N = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    solve(s, pmx);  
    reverse(a + 1, a + N + 1);
    solve(s, smx);
    reverse(smx + 1, smx + N + 1);
    int ans = 0;
    for(int i = 1; i <= N; i++) ans = max(ans, pmx[i] + smx[i + 1]);
    cout << ans;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏专注 Java 基础分享

Hibernate框架学习之注解映射实体类

     前面的相关文章中,我们已经介绍了使用XML配置文件映射实体类及其各种类型的属性的相关知识。然而不论是时代的潮流还是臃肿繁杂的配置代码告诉我们,注解配置...

2099
来自专栏me的随笔

Redis中的数据结构与常用命令

对于Redis的介绍这里只写一句:Redis是一种基于内存的高性能非关系型数据库,它以kye-value的形式来存储数据。

1123
来自专栏应兆康的专栏

Python Web - Flask笔记5

MySQL Workbench是一款专为MySQL设计的ER/数据库建模工具。它是著名的数据库设计工具DBDesigner4的继任者。你可以用MySQL Wor...

1461
来自专栏编程坑太多

Mybatis入门到精通

841
来自专栏程序员的SOD蜜

左求值表达式,堆栈,调试陷阱与ORM查询语言的设计

1,表达式的求值顺序与堆栈结构 “表达式” 是程序语言一个很重要的术语,也是大家天天写的程序中很常见的东西,但是表达式的求值顺序一定是从左到右么? C/C++语...

3256
来自专栏积累沉淀

干货--Hadoop自定义数据类型和自定义输入输出格式整合项目案例

正文开始前 ,先介绍几个概念 序列化 所谓序列化,是指将结构化对象转化为字节流,以便在网络上传输或写到磁盘进行永久存储。 反序列化 是指将字节流转回到结构化...

5646
来自专栏JackieZheng

Hadoop阅读笔记(六)——洞悉Hadoop序列化机制Writable

  酒,是个好东西,前提要适量。今天参加了公司的年会,主题就是吃、喝、吹,除了那些天生话唠外,大部分人需要加点酒来作催化剂,让一个平时沉默寡言的码农也能成为一个...

2215
来自专栏我叫刘半仙

原自己手写一个Mybatis框架(简化)

       继上一篇手写SpringMVC之后,我最近趁热打铁,研究了一下Mybatis。MyBatis框架的核心功能其实不难,无非就是动态代理和jdbc的操...

1.8K6
来自专栏个人分享

MapReduce格式与类型

  MapReduce是一个简单的数据处理模型,map与reduce的输入和输出类型都为key-value形式的键值对。

1241
来自专栏IT可乐

mybatis 详解(二)------入门实例(基于XML)

  通过上一小节,mybatis 和 jdbc 的区别:https://cloud.tencent.com/developer/article/1012781,...

2566

扫码关注云+社区