d265 - 10165 - Stone Game

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個兩人輪流拿石頭的遊戲，給定 N 堆石頭，每堆有 Pi 個石頭。Jack 先手，每次可以從任意一堆石頭中拿走至少一個石頭，直到沒有石頭可以拿。判斷 Jack 是否必勝。

解題思路

這道題是經典的 Nim 遊戲。Nim 遊戲的必勝策略是計算所有石頭堆數量的異或值（XOR）。如果異或值為 0，則後手必勝；如果異或值不為 0，則先手必勝。

程式碼中，我們遍歷每一堆石頭的數量，並將它們的異或值累加到 ans 變數中。最後，如果 ans 不為 0，則 Jack 必勝，輸出 "Yes"；否則，Jack 必敗，輸出 "No"。

複雜度分析

• 時間複雜度: O(n)
• 空間複雜度: O(1)

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n;
	while(cin >> n){
		if(n==0)break;
		int ans=0,t=0;
		while(n--){
			cin >> t;
			ans^=t;
		}
		if(ans)
			cout << "Yes\n";
		else
			cout << "No\n";
	}
}