Uva 11489 Integer Game－louisfghbvc的部落格

題目連結: 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";
    }
}
/**

**/