AtCoder Beginner Contest 172.F - Unfair Nim

朱高超
2023-12-01

AtCoder Beginner Contest 172.F - Unfair Nim

传送门

思路:异或的性质+构造。

显然题目背景是 N i m Nim Nim游戏,我们目的是让后手胜,显然 n n n堆石子异或为 0 0 0时,后手必胜。接下我们需要构造来使 n n n堆石子异或和为 0 0 0

因为题目要求我们只能将移动第一堆石子给第二堆石子。

我们记第一堆和第二堆石子个数分别为 a , b a,b a,b

所以我们可以预处理第 3 3 3堆到第 n n n堆石子的异或和,我们记为 c c c

设需要移动的石子数为 x x x个。

即我们要使: ( a − x ) ⊕ ( b + x ) ⊕ c = 0 → ( a − x ) ⊕ ( b + x ) = c (a-x)\oplus(b+x)\oplus c=0\rightarrow (a-x)\oplus (b+x)=c (ax)(b+x)c=0(ax)(b+x)=c

首先我们需要知道几个结论:

1: a 1 ⊕ a 2 ⋯ ⊕ a n ≤ ∑ i = 1 n a i a_1\oplus a_2\dots \oplus a_n\leq \sum\limits_{i=1}^n a_i a1a2ani=1nai

n n n个数异或和不能大于其求和。显然取等当这个 n n n个数两两的 1 1 1所在位不同。

2.异或和与求和奇偶性相同。

3.要构造长度为2的数组。

最开始满足的条件是 z ⊕ z ⊕ x = 0 , z = y − x 2 , x 是 异 或 和 , y 是 求 和 。 z\oplus z\oplus x=0,z=\dfrac{y-x}{2},x是异或和,y是求和。 zzx=0,z=2yxxy

当且仅当 ( z & x ) = = 0 (z\&x)==0 (z&x)==0,长度才能变为2。即 z , x z,x z,x两个数1的位完全不同,因此才能满足 z ⊕ x = z + x z\oplus x=z+x zx=z+x.

以上证明如果不懂可以看看之前的博客写的一个类似的题,相信会有更清楚的理解。
博客链接

因此我们可以先排除一些不可能的答案。

s = a + b , d = ( s − c ) , a n s = d / 2 s=a+b,d=(s-c),ans=d/2 s=a+b,d=(sc),ans=d/2

( ( d & 1 ) ∣ ∣ ( d < 0 ) ∣ ∣ ( a n s > a ) ∣ ∣ ( a n s & c ) ) ((d\&1)||(d<0)||(ans>a)||(ans\&c)) ((d&1)(d<0)(ans>a)(ans&c)) 是不可能的情况。

第一个对应性质2,第二个对应性质1,第三个是要当前最小的构造 z z z必须不能大于 a a a

第四个是性质3.

因为题目是要求拿走的石子数最少,即 a n s ans ans要在 ≤ a \leq a a的情况下最大。

因为 a n s , ( a n s ⊕ c ) ans,(ans\oplus c) ans,(ansc)前一个数的 1 1 1所在位,后面全部有,且 a n s , c ans,c ans,c的1位不同。(性质3)

所以我们只需要从 c c c里拿 1 1 1过来给前面一个数,让 a n s ans ans变大。

所以枚举一下 c c c的1的位就解决了此题。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5,M=1e6+5,inf=0x3f3f3f3f,mod=1e9+7;
#define mst(a) memset(a,0,sizeof a)
#define lx x<<1
#define rx x<<1|1
#define reg register
#define PII pair<int,int>
#define fi first 
#define se second
int main(){
	int n;
	ll a,b,c=0;
	scanf("%d%lld%lld",&n,&a,&b);
	for(int i=3;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		c^=x;
	} 	
	ll s=a+b,d=(s-c),ans=d/2;
	if((d&1)||d<0||ans>a||(ans&c)) return puts("-1"),0;
	for(ll i=(1LL<<61);i;i>>=1){
		if((i&c)&&ans+i<=a) ans+=i; 
	}
	printf(ans?"%lld\n":"-1\n",a-ans);
	return 0;
}
 类似资料: