P4136 谁能赢呢？ 题解

Bc2_Ch1ckenPr1nce · 2023-06-27 22:12:30 · 题解

P4136 谁能赢呢？ 题解

题目分析

我们可以发现，两人显然都用的是最优的策略，尽量走过所有的格子。那么，我们可以推出当 n \bmod 2 = 0 时，n^2 - 1 必为奇数，这样先手就会让后手无路可走并不浪费任何格子取得胜利。而当 n \bmod 2 = 1 时，后手则会胜利。

则题目可以变为 n \bmod 2 = 1 时输出 Bob，n \bmod 2 = 0 输出 Alice。

code

#include<bits/stdc++.h>  
using namespace std; 
#define int long long
#define qwq ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const int N = -1;

signed main()
{ 
    qwq;
    int n;
    while (cin >> n)
    {
        if (n == 0)
            break;
        if (n & 1)
            cout << "Bob" << endl;
        else
            cout << "Alice" << endl;
    }
    return 0;  
}