每天一道博弈论之“肥猫的游戏”

梦里梦外; 2021-12-18 06:29 205阅读 0赞

##  题链：[https://www.luogu.org/problemnew/show/P1488][https_www.luogu.org_problemnew_show_P1488] ##

#  题解： #

容易发现当黑色三角形在最外面的时候先手胜。

那么接下来考虑黑色三角在里面的情况。因为双方都会尽力避免让黑色三角露在外面，所以必败态为两个白色三角夹着一个黑色三角。又因为每次双方都只能取一个，所以当（n-3）为奇数时先手胜，否则后手胜。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<iostream>
     2 #include<cstdio>
     3 #include<cstring>
     4 #define LL long long
     5 #define RI register int
     6 using namespace std;
     7 const int INF = 0x7ffffff ;
     8 const int N = 50000 + 10 ;
     9 
    10 inline int read() {
    11     int k = 0 , f = 1 ; char c = getchar() ;
    12     for( ; !isdigit(c) ; c = getchar())
    13       if(c == '-') f = -1 ;
    14     for( ; isdigit(c) ; c = getchar())
    15       k = k*10 + c-'0' ;
    16     return k*f ;
    17 }
    18 int n, s[N] ;
    19 
    20 int main() {
    21     n = read() ; n -= 2 ;
    22     int sx = read(),sy = read(), sz = read() ;
    23     s[sx]++, s[sy]++, s[sz]++ ;
    24     for(int i=1;i<n;i++) {
    25         int x = read(), y = read(), z = read() ;
    26         s[x]++, s[y]++, s[z]++ ;
    27     }
    28     n -- ;
    29     if(s[sx] == 1 || s[sy] == 1 || s[sz] == 1) {
    30         printf("JMcat Win\n") ;
    31     } else if(n&1) {
    32         printf("JMcat Win\n") ;
    33     } else printf("PZ Win\n") ;
    34     return 0 ;
    35 }

转载于:https://www.cnblogs.com/zub23333/p/8604177.html

[https_www.luogu.org_problemnew_show_P1488]: https://www.luogu.org/problemnew/show/P1488
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211218/fa598f97dff94ecd8c07d0e0aac8ab30.png