【题解】Luogu P5283 [十二省联考2019]异或粽子

原题传送门

看见一段的异或和不难想到要做异或前缀和\(s\)

我们便将问题转化成：给定\(n\)个数，求异或值最靠前的\(k\)对之和

我们珂以建一个可持久化01trie，这样我们就珂以求出每个值\(s[a]\)与之前所有的值异或值最大的值\(b\)是多少，把这些所有\((b,a)\)塞进一个堆中

每次从堆顶取元素，设这个元素为\((b,a)\)，要将\(b\)加入答案，并且在版本\(a\)的01trie中减去\(s[a]\)^\(b\)，再取出\(s[a]\)与01trie中的数异或最大值（原来的次大值）\(c\)，把\((c,a)\)塞进这个堆中

重复做k次即可得到答案

#include <bits/stdc++.h>

#define N 500005

#define uint unsigned int

#define ll long long

#define getchar nc

using namespace std;

inline char nc(){

    static char buf[100000],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;

}

inline uint read()

{

    register uint x=0;register char ch=getchar();

    while(ch<'0'||ch>'9')ch=getchar();

    while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

    return x;

}

inline void write(register ll x)

{

    if(!x)putchar('0');if(x<0)x=-x,putchar('-');

    static int sta[20];register int tot=0;

    while(x)sta[tot++]=x%10,x/=10;

    while(tot)putchar(sta[--tot]+48);

}

int n,k;

ll ans=0;

uint a[N],b[N];

priority_queue< pair<ll,ll> > q;

struct node{

	int sum,ch[2];

}tr[N*60];

int root[N],tot;

inline void update(register int &x,register int pre,register uint val,register int dep)

{

	x=++tot;

	tr[x]=tr[pre];

	++tr[x].sum;

	if(dep==-1)

		return;

	if((1ll<<dep)&val)

		update(tr[x].ch[1],tr[pre].ch[1],val,dep-1);

	else

		update(tr[x].ch[0],tr[pre].ch[0],val,dep-1);

}

inline uint query(register int x,register uint val,register int dep)

{

	if(dep==-1)

		return 0;

	if(val&(1ll<<dep))

	{

		if(tr[tr[x].ch[0]].sum)

			return query(tr[x].ch[0],val,dep-1);

		else

			return query(tr[x].ch[1],val,dep-1)+((uint)1<<dep);

	}

	else

	{

		if(tr[tr[x].ch[1]].sum)

			return query(tr[x].ch[1],val,dep-1)+((uint)1<<dep);

		else

			return query(tr[x].ch[0],val,dep-1);

	}

}

inline void modify(register int &x,register int pre,register uint val,register int dep)

{

	x=++tot;

	tr[x]=tr[pre];

	--tr[x].sum;

	if(dep==-1)

		return;

	if((1ll<<dep)&val)

		modify(tr[x].ch[1],tr[pre].ch[1],val,dep-1);

	else

		modify(tr[x].ch[0],tr[pre].ch[0],val,dep-1);

}

int main()

{

	n=read(),k=read();

	b[0]=0;

	for(register int i=1;i<=n;++i)

	{

		a[i]=read();

		b[i]=b[i-1]^a[i];

	}

	for(register int i=1;i<=n;++i)

		update(root[i],root[i-1],b[i-1],31);

	for(register int i=1;i<=n;++i)

	{

		uint tmp=query(root[i],b[i],31);

		q.push(make_pair(tmp^b[i],i));

	}

	while(k--&&!q.empty())

	{

		pair<ll,ll> tmp=q.top();

		q.pop();

		ans+=tmp.first;

		int pos=tmp.second;

		modify(root[pos],root[pos],tmp.first^b[pos],31);

		if(!tr[root[pos]].sum)

			continue;

		uint tmpp=query(root[pos],b[pos],31);

		q.push(make_pair(b[pos]^tmpp,pos));

	}

	write(ans);

	return 0;

}

巴特西

【题解】Luogu P5283 [十二省联考2019]异或粽子

原题传送门

看见一段的异或和不难想到要做异或前缀和\(s\)

我们便将问题转化成：给定\(n\)个数，求异或值最靠前的\(k\)对之和

我们珂以建一个可持久化01trie，这样我们就珂以求出每个值\(s[a]\)与之前所有的值异或值最大的值\(b\)是多少，把这些所有\((b,a)\)塞进一个堆中

每次从堆顶取元素，设这个元素为\((b,a)\)，要将\(b\)加入答案，并且在版本\(a\)的01trie中减去\(s[a]\)^\(b\)，再取出\(s[a]\)与01trie中的数异或最大值（原来的次大值）\(c\)，把\((c,a)\)塞进这个堆中

重复做k次即可得到答案

最新文章

热门文章