题目描述
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
输入格式
第一行包含整数 n。
第二行包含 n 个数字,其中第 i 个数字表示第 i 堆石子的数量。
输出格式
如果先手方必胜,则输出 Yes。
否则,输出 No。
数据范围
1≤n≤105,
1≤每堆石子数≤109
样例
输入样例:
2
2 3
输出样例:
Yes
算法1
(博弈论) $O(n)$
给定n中状态:a1,a2,a3.....an;
如果有:a1^a2^a3^a4^…^an=0;则先手必败
a1^a2^a3^a4^…^an!=0;则先手必胜
证明:当所有的石子都被拿完之后,0^0^0^0…^0=0
所以当a1^a2^a3^a4^…^an最初状态就是0是完结状态,就是已经输了
证明:当a1^a2^a3^a4^…^an!=0时先手必胜
设:a1^a2^a3^a4^…^an=x!=0
设x的二进制中最高一位“1”在第k位
a1~an中必有一个ai (ai的第k位是“1”)
旁证:ai^x<ai
举例:设ai=11001001101
^ x = 1010010
=11000......
其第k位的1一定会变成0,又因为k是其最高位的0
那么ai ^ x < ai
所以只要从第ai堆里拿走ai-(ai^x)个,就可以使a1^a2^a3^a4^...^ai'....^an
=a1^a2^a3^a4^...^an^x=x^x=0;
此时也就是完成状态(没有石子可以拿了)
证明:当a1^a2^a3^a4^…^an=x=0时,无论怎么拿,最后的结果都不是0(最后的结果一定是有石子可以拿)
使用反证法:设 如果拿了之后a1^a2^a3^a4^…^an=0;(一号式子)
那么a1^a2^a3^a4^…^ai’^…^an=0;(二号式子)
将1号式子^2号式子(左^左,右^右)
得a1^a2^a3^a4^…^an^a1^a2^a3^a4^…^ai’^…^an=0
又因为:a1^a1=0,a2^a2=0
所以化简可得ai^ai’=0
ai’=ai(这表示没有拿ai堆的石子,这不符合条件,所以不成立)
这道题只需要逐个读入,然后一个一个异或一下,得到结果为0就No,反之则Yes
时间复杂度
参考文献
C++ 代码
#include<iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int res=0;
while(n--)
{
int t;
cin>>t;
res^=t;
}
if(res)puts("Yes");
else puts("No");
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla