結果

問題 No.3112 Decrement or Mod Game
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 13:16:11
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 4,124 bytes
コンパイル時間 842 ms
コンパイル使用メモリ 77,584 KB
実行使用メモリ 617,504 KB
最終ジャッジ日時 2025-04-19 13:16:16
合計ジャッジ時間 4,424 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 MLE * 1 -- * 62
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream> // 用于标准输入输出流
#include <map>      // 用于实现记忆化存储
#include <utility>  // 用于 std::pair

using namespace std;

// 使用 unsigned long long 来处理可能非常大的整数 (高达 10^18)
typedef unsigned long long ull;

// 记忆化表：存储状态 (a, b) 的结果
// 键：pair<ull, ull> 表示状态（当前玩家的数字，对手的数字）
// 值：bool，如果当前玩家能从该状态获胜则为 true，否则为 false
map<pair<ull, ull>, bool> memo;

// 递归函数，判断当前玩家是否能从状态 (a, b) 获胜
// a: 当前玩家的数字
// b: 对手的数字
bool solve(ull a, ull b) {
    // 基本情况 1: 当前玩家数字为 0，意味着轮到该玩家时游戏已经结束，他输了。
    if (a == 0) return false;
    // 基本情况 2: 对手数字为 0，意味着轮到当前玩家时，对手已经输了，当前玩家获胜。
    if (b == 0) return true;

    // 检查记忆化表，如果该状态已经计算过，则直接返回结果
    pair<ull, ull> state = {a, b};
    if (memo.count(state)) {
        return memo[state];
    }

    // 存储当前状态的胜负结果，默认为 false (无法获胜)
    bool can_win = false;

    // 优化：如果 a >= 2b，当前玩家存在必胜策略。(b > 0 已由前面的 b == 0 判断保证)
    // 这个优化常见于类似欧几里得算法的游戏。
    if (a >= 2 * b) {
        can_win = true;
    }
    // 情况 1: a < b
    else if (a < b) {
        // 唯一的操作是将 a 减 1
        ull next_a = a - 1;
        // 如果减 1 后 a 变为 0，当前玩家立即获胜
        if (next_a == 0) {
            can_win = true;
        } else {
            // 否则，当前玩家获胜，当且仅当对手从下一个状态 (b, next_a) 出发会输掉游戏。
            // 对手输掉意味着 solve(b, next_a) 返回 false。
            can_win = !solve(b, next_a);
        }
    }
    // 情况 2: b <= a < 2b
    else {
        // 玩家可以选择两种操作：
        // 操作 1: a -> a % b
        ull next_a_mod = a % b;
        bool win_via_mod = false;
        // 如果取模后 a 变为 0，当前玩家立即获胜
        if (next_a_mod == 0) {
            win_via_mod = true;
        } else {
            // 否则，当前玩家获胜，当且仅当对手从下一个状态 (b, next_a_mod) 出发会输掉游戏。
            win_via_mod = !solve(b, next_a_mod);
        }

        // 如果通过取模操作已经能获胜，则不必考虑减 1 操作
        if (win_via_mod) {
            can_win = true;
        } else {
            // 操作 2: a -> a - 1
            ull next_a_sub = a - 1;
            bool win_via_sub = false;
            // 如果减 1 后 a 变为 0，当前玩家立即获胜
            if (next_a_sub == 0) {
                win_via_sub = true;
            } else {
                // 否则，当前玩家获胜，当且仅当对手从下一个状态 (b, next_a_sub) 出发会输掉游戏。
                win_via_sub = !solve(b, next_a_sub);
            }
            // 当前玩家获胜，如果减 1 操作能导致获胜（因为取模操作不能）
            can_win = win_via_sub;
        }
         // 最终逻辑：如果存在任何一个操作可以获胜，则当前状态可获胜。
         // (上面嵌套的 if-else 已经实现了这个逻辑)
         // bool final_win_mod = (a % b == 0) || !solve(b, a % b);
         // bool final_win_sub = (a - 1 == 0) || !solve(b, a - 1);
         // can_win = final_win_mod || final_win_sub; // 这行代码等价于上面的 if-else 结构
    }

    // 将计算结果存入记忆化表并返回
    return memo[state] = can_win;
}

int main() {
    // 加速 C++ 输入输出流
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ull a, b; // Alice 的初始数字 A，Bob 的初始数字 B
    cin >> a >> b;

    // 调用 solve(a, b) 来确定 Alice（先手玩家）是否获胜。
    if (solve(a, b)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0