891.Nim游戲
給定 n 堆石子，兩位玩家輪流操作，每次操作可以從任意一堆石子中拿走任意數量的石子（可以拿完，但不能不拿），最后無法進行操作的人視為失敗，
問如果兩人都采用最優策略，先手是否必勝，
輸入格式
第一行包含整數 n，
第二行包含 n 個數字，其中第 i 個數字表示第 i 堆石子的數量，
輸出格式
如果先手方必勝，則輸出 Yes，
否則，輸出 No，
資料范圍
1≤n≤105,
1≤每堆石子數≤109
輸入樣例：
2
2 3
輸出樣例：
Yes
本題思路
公平組合游戲：
若一個游戲滿足：
- 由兩名玩家交替行動
- 在游戲進行的任意時刻，可以執行合法行動與輪到哪位玩家無關
- 不能行動的玩家判負
eg:圍棋不是公平組合游戲
解釋必勝狀態和必敗狀態：
必勝狀態：先手進行某一特定操作，留給后手的只有失敗，對于先手來說是必勝狀態
必敗狀態：先手無論如何操作，留給后手的只有必勝狀態，對于先手來說是必敗狀態
操作步驟
分別有兩堆：2，3
- 先手從第二堆拿走一個，此時第二堆與第一堆數目相同
- 無論后手怎么拿，先手對后手
鏡像操作，即后手與先手操作相同
本題結論
假設n堆石子，分別為a1,a2,a3,……,an，如果a1⊕ a2⊕ a3⊕,……,⊕ an≠0，先手必勝，否則先手必敗.
最終結果0⊕0⊕0⊕0,……,⊕0=0
結論證明
在操作程序中，如果a1⊕ a2⊕ a3⊕,……,⊕ an=x≠0,那么玩家一定會通過拿走某一堆中的石子導致結果變為零，
- 證明：假設x的二進制最高不為0位在第k位，在a1,a2,……an種必有一個ai,ai的第k位為1,使得ai⊕x<ai;
那么從第i堆拿走(ai-ai⊕x)個石子后，第i堆還剩ai-(ai-ai⊕x)=ai⊕x;
則a1⊕ a2⊕ a3⊕,……,⊕ an=x⊕x=0
如果a1⊕ a2⊕ a3⊕,……,⊕ an=0，無論怎么先手，都會使得a1⊕ a2⊕ a3⊕,……,⊕ an≠0，
- 證明：假設從第i堆拿走一些石子，原有ai個石子，現有ai’個石子，反證法：如果a1⊕ a2⊕ ai’⊕,……,⊕ an=0,則
（a1⊕ a2⊕ a3⊕,……,⊕ an）⊕（a1⊕ a2⊕ ai⊕,……,⊕ an）=ai⊕ai’=0,即ai=ai’，矛盾，所以a1⊕ a2⊕ a3⊕,……,⊕ an=0，無論怎么先手，都會使a1⊕ a2⊕ a3⊕,……,⊕ an≠0，
c++
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int res=0;
for(int i=0;i<n;i++)
{
int x;
cin>>x;
res^=x;
}
if(res==0)puts("No");
else puts("Yes");
return 0;
}
java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner=new Scanner(System.in);
int n=scanner.nextInt();
int res=1;
for(int i=0;i<n;i++)
{
int a=scanner.nextInt();
res^=a;
}
System.out.println((res^1)!=0?"Yes":"No");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/301368.html
標籤：其他
上一篇：【Unity3D 靈巧小知識點】 ?? | 層級面板中的 ‘小手指‘ 作用: 在Scen中將該物體設定為不可選中狀態
下一篇：飛機大戰C++