首页 > 其他 > 详细

BZOJ4260 Codechef REBXOR

时间:2020-01-21 21:41:28      阅读:33      评论:0      收藏:0      [点我收藏+]

标签:不包含   code   spa   一个   插入   xor   

题意:

给出一个含\(N\)个元素的数组\(A\),下标从\(1\)开始,请找出下列式子的最大值:
\[ (A[l_1]\oplus A[l_1+1]\oplus\dots\oplus A[r_1])+(A[l_2]\oplus A[l_2+1]\oplus\dots A[r_2]) \]

其中\(1\leq l_1 \leq r_1 < l_2 \leq r_2\leq N\)

思路:

01字典树。当然会了一点简单的题,这个还是没有一点思路,之前的都是跑一个数的最大值,这里是区间。这里用到了简单的异或性质

  • \(0\oplus a = a, a\oplus a = 0\)

所以这里用到了前缀异或和\(pre[i]\),后缀异或和\(suf[i]\)

\(pre[i]\oplus pre[j] = a[i+1]\oplus a[i+2]\oplus\dots\oplus a[j], i < j\),后缀同理

所以我们可以利用\(dp\)思想,\(dp[i]\)表示前\(i\)个数的任意区间最大值。

通过查询\(pre[i]\)来获得任意区间的最大值---->利用上面的性质。

每次再把\(pre[i]\)插入到字典树中。

对于后缀,为了使区间不相交,这里跑\(suf[i]\)包含第\(i\)个数,所以为\(Query(suf[i])+dp[i-1]\),让前缀不包含第\(i\)个数。

#include<bits/stdc++.h>
using namespace std;
const int N = 400010;
const int inf = 0X3f3f3f3f;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-6;
const double pi = acos(-1.0);
const int mod = 1000000007;
typedef long long ll;

int n;
int a[N];
int pre[N], suf[N];
int dp[N];
int tri[32 * N][2];
int val[32 * N];
int tot;

void init() {
    memset(tri, 0, sizeof(tri));
    memset(val, 0, sizeof(val));
    tot = 1;
}

void Insert(int x) {
    int u = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (x & (1 << i)) ? 1 : 0;
        if (!tri[u][bit])
            tri[u][bit] = tot++;
        u = tri[u][bit];
    }
    val[u] = x;
}

int Query(int x) {
    int u = 0;
    for (int i = 31; i >= 0; i--) {
        int bit = (x & (1 << i)) ? 1 : 0;
        if (tri[u][bit ^ 1])
            u = tri[u][bit ^ 1];
        else
            u = tri[u][bit];
    }
    return x ^ val[u];
}

int main() {
    while(~scanf("%d", &n)) {
        init();
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        pre[0] = suf[n + 1] = 0;
        for (int i = 1; i <= n; i++) pre[i] = pre[i - 1] ^ a[i];
        for (int i = n; i >= 1; i--) suf[i] = suf[i + 1] ^ a[i];
        Insert(pre[0]);
        for (int i = 1; i <= n; i++) {
            dp[i] = max(dp[i - 1], Query(pre[i]));
            Insert(pre[i]);
        }
        init();
        Insert(suf[n + 1]);
        int ans = -1;
        for (int i = n; i >= 1; i--) {
            ans = max(ans, Query(suf[i]) + dp[i - 1]);
            Insert(suf[i]);
        }
        printf("%d\n", ans);
    }
}

BZOJ4260 Codechef REBXOR

标签:不包含   code   spa   一个   插入   xor   

原文:https://www.cnblogs.com/ACMerszl/p/12225784.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号