結果

問題 No.3112 Decrement or Mod Game
コンテスト
ユーザー aaaaaaaaaaa
提出日時 2025-04-19 10:37:12
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
MLE  
実行時間 -
コード長 3,796 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,252 ms
コンパイル使用メモリ 82,584 KB
実行使用メモリ 816,256 KB
最終ジャッジ日時 2025-04-19 10:37:19
合計ジャッジ時間 5,833 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other MLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <string>
#include <map>
#include <tuple>
#include <algorithm>

using namespace std;

// 使用 map 来存储已经计算过的状态及其结果，避免重复计算
// tuple<long long, long long, bool> 作为 key：(a的值, b的值, 是否是Alice的回合)
// bool 作为 value：当前玩家是否能赢
map<tuple<long long, long long, bool>, bool> memo;

// 递归函数，判断当前玩家是否能从状态 (a, b) 赢
// a: Alice拥有的数字, b: Bob拥有的数字, is_alice_turn: 当前是否是Alice的回合 (true为Alice, false为Bob)
// 返回值：true 表示当前玩家能赢，false 表示当前玩家会输
bool solve(long long a, long long b, bool is_alice_turn) {
    // 游戏结束的条件：如果一个玩家的数字变为0，则使该数字变为0的玩家获胜。
    // 函数的输入 (a, b) 是当前回合开始时的数字。如果 a 或 b 已经是0，说明上一回合的玩家
    // 使其数字变为了0并取得了胜利。因此，当前回合的玩家是输家。
    if (a == 0) return false; // 当前玩家 (Alice) 的数字是0，说明Bob赢了
    if (b == 0) return false; // 当前玩家 (Bob) 的数字是0，说明Alice赢了

    // 检查当前状态是否已计算过
    tuple<long long, long long, bool> current_state = {a, b, is_alice_turn};
    if (memo.count(current_state)) {
        return memo[current_state];
    }

    bool can_win; // 标记当前玩家是否能赢

    if (is_alice_turn) {
        // Alice的回合 (拥有数字 a)

        // Alice 可以执行的操作：
        // 1. 将 a 减 1。新状态 (a-1, b)，轮到Bob。
        //    如果Bob从 (a-1, b) 输了，则Alice赢。
        bool win_dec = !solve(a - 1, b, false);

        // 2. 将 a 替换为 a % b (仅当 a >= b 时可执行)。新状态 (a%b, b)，轮到Bob。
        //    如果Bob从 (a%b, b) 输了，则Alice赢。
        bool win_mod = false; // 默认modulo操作不能赢或不可执行
        if (a >= b) {
            long long rem = a % b;
            win_mod = !solve(rem, b, false);
        }
        
        // Alice 能赢当且仅当 她可以通过至少一种操作到达一个 Bob 会输的状态。
        if (a < b) {
            // 如果 a < b，Alice 只能执行减1操作
            can_win = win_dec;
        } else {
            // 如果 a >= b，Alice 可以选择执行减1或modulo操作
            can_win = win_dec || win_mod;
        }

    } else {
        // Bob的回合 (拥有数字 b)

        // Bob 可以执行的操作：
        // 1. 将 b 减 1。新状态 (a, b-1)，轮到Alice。
        //    如果Alice从 (a, b-1) 输了，则Bob赢。
        bool win_dec = !solve(a, b - 1, true);

        // 2. 将 b 替换为 b % a (仅当 b >= a 时可执行)。新状态 (a, b%a)，轮到Alice。
        //    如果Alice从 (a, b%a) 输了，则Bob赢。
        bool win_mod = false; // 默认modulo操作不能赢或不可执行
        if (b >= a) {
            long long rem = b % a;
            win_mod = !solve(a, rem, true);
        }

        // Bob 能赢当且仅当 他可以通过至少一种操作到达一个 Alice 会输的状态。
        if (b < a) {
            // 如果 b < a，Bob 只能执行减1操作
            can_win = win_dec;
        } else {
            // 如果 b >= a，Bob 可以选择执行减1或modulo操作
            can_win = win_dec || win_mod;
        }
    }

    // 存储并返回计算结果
    return memo[current_state] = can_win;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    long long A, B;
    cin >> A >> B;

    // 游戏从Alice开始
    if (solve(A, B, true)) {
        cout << "Alice" << endl;
    } else {
        cout << "Bob" << endl;
    }

    return 0;
}
0