UOJ Logo zhouzixuan的博客

博客

bzoj 4260: Codechef REBXOR

2015-09-22 13:17:00 By zhouzixuan
【题目描述】:

【题目解法】:
    不要被tag吓倒了,其实是个SB经典题辣
    我们枚据一下分割点,变成两边去最大值
    我们考虑一边,我们可以弄出前缀异或
    然后变成两个数异或最大,直接上主席树拆位贪心即可
    然后在弄个后缀
    两边加起来max一下就好
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=400005;
const int M=32;
struct point {int son[2];} tree[N*M];
int n,a[N],b[N],tot,root[N],f[N],g[N],ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint();
    for (int i=1; i<=n; i++) a[i]=getint();
}
inline void add(int x)
{
    int p=1;
    for (int i=30; i>=0; i--)
    {
        int now=(x>>i)&1;
        if (tree[p].son[now]==0) tree[p].son[now]=++tot;
        p=tree[p].son[now];
    }
}
inline int ask(int x)
{
    int p=1,nowans=0;
    for (int i=30; i>=0; i--)
    {
        int now=(x>>i)&1;
        if (tree[p].son[1-now]) nowans+=(1<<i),p=tree[p].son[1-now];
        else p=tree[p].son[now];
    }
    return nowans;
}
void solve()
{
    tot=1; memset(tree,0,sizeof(tree)); add(0);
    for (int i=1; i<=n; i++) b[i]=b[i-1]^a[i];
    for (int i=1; i<=n; i++) f[i]=ask(b[i]),add(b[i]);
}
void Rev()
{
    for (int i=1; i<=n; i++) g[i]=f[i];
    for (int i=1; i<=n/2; i++) swap(a[i],a[n-i+1]);
}
void GetAns()
{
    ans=0;
    for (int i=1; i<=n; i++) f[i]=max(f[i],f[i-1]);
    for (int i=1; i<=n; i++) g[i]=max(g[i],g[i-1]);
    for (int i=1; i<=n/2; i++) swap(g[i],g[n-i+1]);
    for (int i=1; i<=n-1; i++) ans=max(ans,f[i]+g[i+1]);
    printf("%d\n",ans);
}
int main()
{
    init();
    solve();
    Rev();
    solve();
    GetAns();
    return 0;
}

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。