洛谷$P$2575 高手过招博弈论

佚名 6年前 (2019-05-11) 随笔 1335人围观抢沙发百度已收录

正解:博弈论

解题报告:

传送门!

阿西$gql$又双叒被题意杀辣,,,再不好好学语文吃枣药丸$TT$

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

然后在$get$规则之后还有什么问题嘛,,,

就和这题差不多了,一个$easy$的阶梯问题罢辽,等下放代码$QAQ$

但是如果这么$easy$我大概就不会放了个阶梯问题板子之后再放一个辣,,,主要这题还可以用$SG$函数,虽然复杂度差很多,然后因为$gql$在这个方面非常差所以目前这个状态来说,大概会把所有做的能用$SG$函数的题都写个题解$QwQ$

欧克然后看这题$SG$函数怎么做鸭$QwQ$

考虑递推出所有状态是必胜还是必败,简单来说,就把每种状态压缩成一个二进制数,然后就能推出所有状态的的$SG$函数,然后对全局的话,直接将每一行的$SG$值异或起来,看是否为0就好,$over$

$umm$懒得放代码了不难,就只写下解法算了$QAQ$(其实是因为懒$bushi$

#include<bits/stdc++.h>
using namespace std;
#define il inline
#define int long long
#define gc getchar()
#define ri register int
#define rb register bool
#define rc register char
#define rp(i,x,y) for(ri i=x;i<=y;++i)

const int N=50;
bool cnt[N];

il int read()
{
    rc ch=gc;ri x=0;rb y=1;
    while(ch!='-' && (ch>'9' || ch<'0'))ch=gc;
    if(ch=='-')ch=gc,y=0;
    while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^'0'),ch=gc;
    return y?x:-x;
}

signed main()
{
    int T=read();
    while(T--)
    {
        ri n=read(),as=0;
        rp(i,1,n)
        {
            memset(cnt,0,sizeof(cnt));ri nw=20,num=0;bool flg=0;
            ri m=read();rp(i,1,m)cnt[read()]=1;
            while(cnt[nw])--nw;
            while(nw)
            {
                if(!cnt[nw])as^=flg?num:0,flg^=1,num=0;else ++num;
                --nw;
            }
            as^=flg?num:0;
        }
        printf(as?"YES\n":"NO\n");
    }
    return 0;
}