AtCoder Beginner Contest 172.F - Unfair Nim

传送门

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

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

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

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

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

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

即我们要使： $(a-x)\oplus(b+x)\oplus c=0\rightarrow (a-x)\oplus (b+x)=c$

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

1： $a_1\oplus a_2\dots \oplus a_n\leq \sum\limits_{i=1}^n a_i$

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

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

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

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

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

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

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

记 $s=a+b,d=(s-c),ans=d/2$

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

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

第四个是性质3.

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

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

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

所以枚举一下 $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;
}