結果

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

ソースコード

diff # 

#include <iostream> // 用于标准输入输出流
#include <vector>   // 虽然未使用，但通常包含在C++标准库中
#include <numeric>  // 虽然未使用，但包含一些数值算法
#include <map>      // 用于存储记忆化结果
#include <utility>  // 用于 std::pair
#include <algorithm> // 用于 std::swap (虽然未使用，但可能需要)

// 使用 long long 类型处理大整数，最大可达 10^18
using ll = long long;

// 使用 map 来存储已经计算过的状态结果，避免重复计算
// 键是 (a, b) 状态对，值是布尔类型表示当前玩家是否能赢
std::map<std::pair<ll, ll>, bool> memo;

// 函数 can_win(a, b) 判断：
// 当前轮到的玩家持有数字 'a'，对手持有数字 'b'，当前玩家是否能够强制获胜？
bool can_win(ll a, ll b) {
    // 基本情况 1: 如果当前玩家的数字 a 为 0
    // 这意味着在上一个对手的回合后，当前玩家的数字变成了0。
    // 根据规则“先将自己数字变成0者获胜”，这意味着对手在上一步没有获胜，
    // 而现在轮到当前玩家时数字已经是0，这似乎有些矛盾。
    // 更准确地说，如果一个玩家通过操作使自己的数字变为0，则该玩家立即获胜。
    // 递归调用的含义是：如果对手从下一个状态无法获胜，则当前玩家获胜。
    // 因此，如果 a=0，表示当前玩家无法进行任何操作使 a 变为 0（因为它已经是0了）。
    // 这通常意味着之前的状态转移有问题，或者这是一个不应该达到的初始状态。
    // 按照游戏逻辑，轮到你时你的数字是0，你应该已经输了。
    if (a == 0) {
        return false;
    }
    // 基本情况 2: 如果对手的数字 b 为 0
    // 这意味着对手在他的上一个回合使得 b=0 并获胜了。
    // 所以当前玩家 (a, 0) 已经输了。
    if (b == 0) {
        return false;
    }

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

    // 优化: 如果 a >= 2b，当前玩家总能获胜。
    // 这个结论的证明基于：如果取模操作不能直接导向胜利（即对手在 (b, a % b) 状态下能赢），
    // 那么可以通过连续的 (a-1, b-1) 转换，最终归结为一个必胜状态。
    // (需要 b > 0，这个条件在上面的 b == 0 判断后是满足的)
    if (a >= 2 * b) {
        memo[state] = true; // 记录结果
        return true;
    }

    // 递归计算：当前玩家获胜，当且仅当存在一个操作，使得操作后的状态对于下一个玩家（即当前对手）来说是必败的。
    // 必败状态意味着 can_win 返回 false。

    // 考虑操作 1: 将自己的数字减 1 (a -> a - 1)
    // 操作后的状态对对手来说是 (b, a - 1)。
    // 当前玩家获胜，如果对手从 (b, a - 1) 状态开始无法获胜。
    // 获胜条件: !can_win(b, a - 1)
    if (!can_win(b, a - 1)) {
        memo[state] = true; // 记录结果
        return true;        // 找到一个获胜策略
    }

    // 考虑操作 2: 将自己的数字替换为 a % b (仅当 a >= b 时可行)
    // 操作后的状态对对手来说是 (b, a % b)。
    // 当前玩家获胜，如果对手从 (b, a % b) 状态开始无法获胜。
    // 获胜条件: !can_win(b, a % b)
    if (a >= b) {
        // 注意：如果 a % b == 0，这个操作直接使当前玩家获胜。
        // 递归调用 !can_win(b, 0) 会返回 !false = true，所以这个情况被正确处理了。
        if (!can_win(b, a % b)) {
            memo[state] = true; // 记录结果
            return true;        // 找到一个获胜策略
        }
    }

    // 如果以上所有可能的操作都不能保证当前玩家获胜（即所有操作都会导向对手的必胜状态）
    // 那么当前玩家处于必败状态。
    memo[state] = false; // 记录结果
    return false;
}

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

    ll a, b; // 输入 Alice 和 Bob 的初始数字
    std::cin >> a >> b;

    // Alice 先手，初始状态是 (A, B)。我们需要判断 Alice 是否能赢。
    if (can_win(a, b)) {
        std::cout << "Alice" << std::endl; // 如果 Alice 能赢
    } else {
        std::cout << "Bob" << std::endl;   // 如果 Alice 不能赢（即 Bob 赢）
    }

    return 0; // 程序正常结束
}
0