b588 - 撿石頭遊戲

🔗 前往 ZeroJudge 原題

題目描述

題目描述了 Arthur 和 Caroll 玩一個撿石頭遊戲，給定三堆石頭的數量，判斷在最佳策略下，先手 Arthur 是否會贏得遊戲。遊戲的規則允許玩家從一堆、兩堆或三堆石頭中拿取相同數量的石頭。

解題思路

這道題是 Nim 遊戲的一個變形。Nim 遊戲的經典解法是計算 Nim 和（每個堆的石頭數量進行異或運算）。如果 Nim 和為 0，則後手玩家必勝；否則，先手玩家必勝。

然而，題目允許同時從多個堆中拿取石頭，這使得直接應用 Nim 和的策略不正確。正確的解法是使用動態規劃 (DP) 來判斷 Arthur 是否會贏。

DP 的狀態可以定義為 dp[x][y][z]，表示當三堆石頭的數量分別為 x、y、z 時，先手玩家是否必勝。

DP 的轉移方程如下： dp[x][y][z] = not (dp[x-i][y][z] and dp[x][y-i][z] and dp[x][y][z-i] and dp[x-i][y-i][z] and dp[x-i][y][z-i] and dp[x][y-i][z-i] and dp[x-i][y-i][z-i])，其中 i 是從 1 開始的拿取數量，且 x-i >= 0, y-i >= 0, z-i >= 0。

如果存在一種拿取方案使得對手必敗，則當前玩家必勝。

然而，題目提供的程式碼並未實現上述 DP 邏輯，而是計算了從 0 到 a 的所有數字的和。這段程式碼無法解決題目所描述的撿石頭遊戲。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入的數字 a。
• 空間複雜度: O(1)

程式碼

#include <iostream>

using namespace std;

int main(){
	
	int a=0;
	long long int s=1;
	
	while(cin >> a){
		
		for(int i=0;i<a;i++){
			s=s+i;
		}
		cout << s <<endl;
		s=1;
	}
}