洛谷5283 [十二省联考2019]异或粽子

Luogu

BZOJ

LOJ

分析

我们先来看一道比这题难的题目:NOI2010 超级钢琴

如果不会做这题,下面是题解链接:

然后发现这题跟超级钢琴相比,就只是限定 $L=1,R=n$ ,然后把和换成了异或和。

那么相应的把主席树换成可持久化 Trie 树就行了,其它地方不怎么需要改。

具体实现及细节见代码。

顺手跑进 BZOJ 第一版

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

inline ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=500000+10;
const int L=31;

int a[N],s[N],rt[N],tot=0;
struct node { int p,cnt; ll val; };
bool operator <(node a,node b) { return a.val<b.val; }
priority_queue<node> Q;

struct Trie {
    struct node { int ch[2],sz; } t[N*40];

    inline void insert(int& p,ll x,int k) {
        t[++tot]=t[p],++t[p=tot].sz;
        if (k<0) return;
        int w=(x>>k)&1;
        insert(t[p].ch[w],x,k-1);
    }

    inline ll query(int p,ll x,int rk,int k) {
        if (k<0) return 0;
        int w=((x>>k)&1)^1,s=t[t[p].ch[w]].sz;
        if (rk<=s) return query(t[p].ch[w],x,rk,k-1)|(1ll<<k);
        else return query(t[p].ch[w^1],x,rk-s,k-1);
    }
} T;

int main() {
    int n=read(),K=read(); T.insert(rt[0],0,L);
    for (re int i=1;i<=n;++i) a[i]=read();
    for (re int i=1;i<=n;++i) s[i]=s[i-1]^a[i];
    for (re int i=1;i<=n;++i) T.insert(rt[i]=rt[i-1],s[i],L);
    for (re int i=1;i<=n;++i) {
        ll v=T.query(rt[i-1],s[i],1,L);
        Q.push((node){i,1,v});
    }
    ll ans=0;
    while (K--) {
        node tp=Q.top(); Q.pop();
        ans+=tp.val; ++tp.cnt;
        if (tp.cnt>tp.p) continue;
        int p=tp.p; ll v=T.query(rt[p-1],s[p],tp.cnt,L);
        Q.push((node){p,tp.cnt,v});
    }
    printf("%lld\n",ans);
    return 0;
}
最后修改:2019 年 09 月 26 日 01 : 24 PM

发表评论