close
題目連結: 11489.pdf (onlinejudge.org)
題目大意: 兩個玩家拿數字,玩家拿數字只能拿讓剩下數字總合為3的倍數,比如1234 可以拿1,因為2+3+4=9
思路: 類似賽局, 前處理先把數字次數記起來。接著用dp, 也就是dfs + memo,dp[i][1] 表示S為True的情況下,總合為i 的結果是可以達到還是不行,
所以說如果是S的情況他就要找是不是有一個1~9的數字使得我現在 總和-數字 整除3,繼續遞迴,S想得到True的結果。另一玩家相反。
更: 以下代碼Uva 可以過 但是ZeroJudge不能過。
你發現了嗎? 超87的bug。i = 0沒考慮到。0是可以選的==。不過沒想到Uva能過,看來測資不夠強。我真菜。以下代碼自行修正。
先說明大家常用的第二種解法,很單純。
事實上,我們把所有數字一個個都先mod 3。然後先算總和。
分兩個情況,
第一種: 總和剛剛好整除3,代表玩家只能拿掉0, 3, 6, 9。那這4個拿的順序不影響,所以可以把這4個出現次數加起來,就變奇偶問題了。
第二種: 總和不整除3,這個時候是這樣子的,你可以拿掉任一數字讓總和整除3。接下來不就回到第一種了嗎。
第二種如果無法拿掉任意數字使得總和整除3,那先手的輸。
代碼:
#include <bits/stdc++.h>
using namespace std;
int dp[10005][2];
bool dfs(vector<int> &cnt, int tot, bool S){
if(dp[tot][S] != -1) return dp[tot][S];
if(S){
bool res = false;
for(int i = 1; i <= 9; ++i){ // 從0開始阿...
if(cnt[i] && tot >= i && (tot - i) % 3 == 0){
cnt[i]--;
res |= dfs(cnt, tot-i, 0);
cnt[i]++;
}
}
return dp[tot][S] = res;
}
else{
bool res = true;
for(int i = 1; i <= 9; ++i){ // 從0開始阿...
if(cnt[i] && tot >= i && (tot - i) % 3 == 0){
cnt[i]--;
res = res & dfs(cnt, tot-i, 1);
cnt[i]++;
}
}
return dp[tot][S] = res;
}
}
int main() {
//cin.tie(0); ios::sync_with_stdio(false);
int T;
cin >> T;
string s;
for(int t = 0; t < T; ++t){
memset(dp, -1, sizeof dp);
printf("Case %d: ", t+1);
cin >> s;
vector<int> fre(10);
int tot = 0;
for(int i = 0; i < s.size(); ++i){
fre[s[i] - '0']++;
tot += (s[i] - '0');
}
if(dfs(fre, tot, 1)){
cout << "S\n";
}
else cout << "T\n";
}
}
/**
**/
文章標籤
全站熱搜