洛谷P1488 肥猫的游戏题解博弈论入门

题目链接：https://www.luogu.org/problem/P1488

其实这道题目我只需要 \(n\) 以及黑色三角形的三个端点编号就可以了。

我们假设在一个 \(n\) 边形中，黑色三角形的端点号分别是 \(a_0, a_1, a_2\) ，且 \(a_0 \lt a_1 \lt a_2\) ，那我其实可以知道：

\(a_0 - a_1\) 边外围的三角形个数是 \(b_0 = a_1 - a_0 - 1\) ；
\(a_1 - a_2\) 边外围的三角形个数是 \(b_1 = a_2 - a_1 - 1\) ；
\(a_2 - a_0\) 边外围的三角形个数是 \(b_2 = a_0 + n - a_2 - 1\) 。

然后我们来思考一下：

如果一开始黑色三角形就有两条边裸露在外面（即存在两个 \(b_i = 0\)），则直接判定先手赢；

否则，因为大家都是绝对聪明的，所以除非万不得已，绝对不会让黑色三角形的边裸露出来，那么总共会取 \(b_0+b_1+b_2-1\) 轮，此时的状态是黑色三角形有两边裸露，另一边紧贴着仅剩下的一个白色三角形，而下一步执行的人获胜。

那么这个时候只需要判断 \(b_0+b_1+b_2\) 是偶数，则先手赢；是奇数，则后手赢。

实现代码如下：

#include <bits/stdc++.h>

using namespace std;

int n, a[3], b[3];

bool win;

int main() {

    cin >> n; for (int i = 0; i < 3; i ++) cin >> a[i];

    sort(a, a+3);

    b[0] = a[1] - a[0] - 1;

    b[1] = a[2] - a[1] - 1;

    b[2] = a[0] + n - a[2] - 1;

    sort(b, b+3);

    if (b[1] == 0) win = true;

    else win = ( (b[0] + b[1] + b[2] - 1) % 2 == 0 );

    puts( win ? "JMcat Win" : "PZ Win" );

    return 0;

}

巴特西

洛谷P1488 肥猫的游戏题解博弈论入门

最新文章

热门文章

巴特西

洛谷P1488 肥猫的游戏 题解 博弈论入门

最新文章

热门文章

洛谷P1488 肥猫的游戏题解博弈论入门