CF1457D XOR-gun

这道题真的把我秀到了，我首先猜了一波结论，打了一个可持久化 \(\text{Trie}\) 加二分的两只 \(\log_2\) 的做法，发现不能 \(PP\) ，然后就一直改到比赛结束还没改过。

然后比完赛的时候改出来了，发现 \(WA\) \(on\) \(51\) ，心想好像比赛时改没改出来好像没什么区别啊。

然后就看了一波别人的题解，发现是一道结论题。。。

我是 \(sb\) 。

题解

你发现如果任意相邻的三个数中存在最高位相同，那么必然可以通过合并后两个来达到目的，也就证明了如果长度大于 \(60\) ，答案就必定为 \(1\) ，小于 \(60\) 的直接暴搜就可以了。

代码如下

可持久化 Trie

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,a[N],b[N];

struct Trie

{

	int now,rt[N];

	struct Node{int data,son[2];}tr[N<<5];

	Trie(){now=0,memset(tr,0,sizeof(tr));}

	void add(int u,int v,int x)

	{

		for(int i=30;i>=0;--i)

		{

			tr[v]=tr[u],tr[v].data++;

			int tmp=(bool)(x&(1<<i));

			tr[v].son[tmp]=++now;

			u=tr[u].son[tmp],v=tr[v].son[tmp];

		}

		tr[v]=tr[u],tr[v].data++;

	}

	int query1(int u,int v,int x)

	{

		int res=0;

		for(int i=30;i>=0;--i)

		{

			int tmp=(bool)(x&(1<<i));

			int data=tr[tr[v].son[tmp^1]].data-tr[tr[u].son[tmp^1]].data;

			if(data) u=tr[u].son[tmp^1],v=tr[v].son[tmp^1],res+=(1<<i);

			else u=tr[u].son[tmp],v=tr[v].son[tmp];

		}

		return res;

	}

	int query2(int u,int v,int x)

	{

		int res=0;

		for(int i=30;i>=0;--i)

		{

			int tmp=(bool)(x&(1<<i));

			int data=tr[tr[v].son[tmp]].data-tr[tr[u].son[tmp]].data;

			if(data) u=tr[u].son[tmp],v=tr[v].son[tmp];

			else u=tr[u].son[tmp^1],v=tr[v].son[tmp^1],res+=(1<<i);

		}

		return res;

	}

}t;

int main()

{

	cin>>n;

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=n;++i) b[i]=b[i-1]^a[i];

	// for(int i=1;i<=n;++i) printf("%d ",b[i]);

	// printf("\n");

	t.rt[0]=++t.now;

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

	{

		t.rt[i]=++t.now;

		t.add(t.rt[i-1],t.rt[i],b[i]);

	}

	int res=1e9+7;

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

	{

		int l=1,r=i-1,tmp=-1;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			int data=t.query1(t.rt[mid-1],t.rt[i-1],b[i]);

			// printf("-------\n");

			// printf("%d %d\n",mid,data);

			if(data>a[i+1]) l=mid+1,tmp=mid;

			else r=mid-1;

		}

		if(b[i]>a[i+1]&&tmp==-1) tmp=0;

		// printf("---%d %d\n",i,tmp);

		if(tmp>=0) res=min(res,i-tmp-1);

	}

	for(int i=2;i<=n;++i)

	{

		int l=i+1,r=n,tmp=-1;

		while(l<=r)

		{

			int mid=(l+r)>>1;

			int data=t.query2(t.rt[i],t.rt[mid],b[i-1]);

			// printf("---%d %d\n",mid,data);

			if(data<a[i-1]) r=mid-1,tmp=mid;

			else l=mid+1;

		}

		if((b[n]^b[i-1])<a[i-1]&&tmp==-1) tmp=n;

		// printf("%d\n",tmp);

		if(tmp>=0) res=min(res,tmp-i);

	}

	if(res>=1e9+7) printf("-1\n");

	else printf("%d\n",res);

	return 0;

}

正解

#include<bits/stdc++.h>

using namespace std;

const int N=1e5+5;

int n,a[N],b[N],res=1e9+7;

int main()

{

	cin>>n;

	for(int i=1;i<=n;++i) scanf("%d",&a[i]);

	for(int i=1;i<=n;++i) b[i]=b[i-1]^a[i];

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

	{

		for(int j=0;j<=32&&i-j>=1;++j)

		{

			for(int k=0;k<=32&&i+1+k<=n;++k)

			if((b[i]^b[i-j-1])>(b[i]^b[i+1+k]))

			res=min(res,j+k);

		}

	}

	if(res>=1e9+7) printf("-1\n");

	else printf("%d\n",res);

}

巴特西

CF1457D XOR-gun

题解

代码如下

可持久化 Trie

正解

最新文章

热门文章