洛谷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;
}
原文地址:https://www.cnblogs.com/codedecision/p/11791380.html