题解 P1488 【肥猫的游戏】

Imakf · 2018-08-28 17:53:28 · 题解

刷博弈论，看到这道题是红色的，我就来了

结果一看???这真的是入门难度？？？恶意评分啊！

首先

读题！

我读这道题目都花了好久，实际上意思就是把一个n边形沿着对角线分割，分成n-2个三角形，在其中选中一个三角形成为黑三角形。然后JMcat , PZ两个人轮流拿走边上的一个三角形，谁能拿走黑三角形谁就赢了。

做法

本蒟蒻的做法就是分类讨论! 分3种情况——黑三角形和多少个三角形相邻。

一、和1个三角形相邻

显而易见，黑三角形本身露在外面，JMcat直接取走，puts("JMcat Win");

二、和2个三角形相邻

好像看不出什么……………………………………………………那就找规律啊

规律如下表

规律便一下出来了

if(n%2==1)  puts("PZ Win");
else puts("JMcat Win");

证明

JMcat的必败点就是如上图所示，每次拿走一个三角形实际上就是删去一个点，所以知道剩下5个点JMcat必败，因为一个人取一次，即可得出结论。

三、和3个三角形相邻

跟情况二一样，找规律

规律：

if(n%2==1)  puts("PZ Win");
else puts("JMcat Win");

实际上这两种情况是一样的，就如上图，拿走一个三角形之后便变成了第二种情况。

证明

与情况二类似，不再赘述

蒟蒻AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
struct tri{
    int a[3];
}h[50000+5];
bool point[50000+5];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n-2;++i)
        for(int j=0;j<3;j++)
            scanf("%d",&h[i].a[j]);
    for(int j=0;j<3;++j)
        point[h[0].a[j]]=true;
    short ans=0;
    for(int i=1;i<n-2;++i){
        int _ans=0;
        for(int j=0;j<3;++j)
            _ans+=point[h[i].a[j]];
        if(_ans==2) ++ans;
    }
    if(ans==1)  puts("JMcat Win");
    else if(ans==2){
        if(n%2) puts("PZ Win");
        else puts("JMcat Win");
    }
    else{
        if(n%2) puts("PZ Win");
        else puts("JMcat Win");
    }
    return 0;
}

SOMEBODY:只要判断奇偶？

他们的程序：

#include<iostream>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==5) //实质上是个打表
        cout<<"JMcat Win";
    else if(n%2==0)
            cout<<"JMcat Win"; 
                else cout<<"PZ Win";
    return 0;
}

事实上这是个打表，没有任何意义，只是数据太水，合某些人胃口罢了。

总结

最后祝大家AK IOI！