f710 - 11489 - Integer Game

🔗 前往 ZeroJudge 原題

題目描述

題目描述了一個兩人輪流移除數字字元的遊戲。玩家輪流從給定的數字字串中移除一個字元。移除字元後，如果剩餘字元組成的數字的各位數字和能被 3 整除，則該移除操作有效。如果玩家無法進行有效移除，則該玩家輸掉遊戲。題目要求判斷在雙方都採取最佳策略的情況下，先手玩家 (S) 還是後手玩家 (T) 獲勝。

解題思路

這題的核心在於觀察數字字串各位數字和的模 3 值。如果初始數字字串的各位數字和的模 3 值為 0，則先手玩家可以移除一個模 3 為 0 的數字，使得剩餘數字的各位數字和的模 3 值仍然為 0。如此一來，無論後手玩家如何操作，先手玩家都可以保持剩餘數字的各位數字和的模 3 值為 0。最終，後手玩家將無法移除任何數字，因此先手玩家獲勝。

如果初始數字字串的各位數字和的模 3 值不為 0，則先手玩家必須移除一個模 3 等於初始數字字串模 3 值的數字，才能使得剩餘數字的各位數字和的模 3 值為 0。如果先手玩家無法移除這樣的數字，則先手玩家會輸掉遊戲。

程式碼中，s[0], s[1], s[2] 分別記錄數字字串中模 3 為 0, 1, 2 的數字個數。t 記錄數字字串的各位數字和的模 3 值。r 記錄先手玩家移除數字的次數。如果 r 為奇數，則先手玩家獲勝；否則，後手玩家獲勝。

複雜度分析

• 時間複雜度: O(n)，其中 n 是數字字串的長度。程式碼遍歷數字字串一次來計算各位數字和的模 3 值和每個模 3 值的數字個數。
• 空間複雜度: O(1)。程式碼使用固定大小的陣列 s 和變數 t, r, al，因此空間複雜度為常數。

程式碼

#include <iostream>
using namespace std;
string a;
int n;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	cin >> n;
	for(int ca=1;ca<=n;++ca){
		cin >> a;
		int al=a.length(),t=0,s[3]={0},r=0;
		for(int i=0;i<al;++i){
			t+=a[i]-'0';
			++s[(a[i]-'0')%3];
		}
		while(s[t%3]){
			++r;
			--s[t%3];
			t=0;
		}
		cout << "Case " << ca << ": ";
		if(r%2)
			cout << "S\n";
		else
			cout << "T\n";
	}
}