HDU1851 A Simple Game

一个关于SG的博弈游戏，对于某个堆有$M_i$和$L_i$,那么这个堆的SG值为

$$SG_i = M_i \%(L_i+1)$$

为什么这道题的$SG$函数就是这样子的呢？四个字：手算打表！！

$Let's \quad Review \quad The \quad Defination \quad Of \quad \quad SG \quad Function!!$

定义$SG(x)=mex(S)$,其中$S$是$x$的后继状态的$SG$函数值集合，$mex(S)$表示不在$S$内的最小非负的整数。

我们先取$L=5$来看一下

当$M=1$时,由于$1$的后继状态只有$0$，由sg定义可得$sg[1] =mex\{sg[0]\}=1$

,当$M=2$时，$2$的后继状态有$0,1$得到$sg[2]= mex\{sg[0],sg[1]\}=2$

当$M=3$时，$3$的后继状态有$0,1,2$有$sg[3] = mex\{sg[0],sg[1],sg[2]\}= mex\{0,1,2\}=3$

$……$

当$M=5$时，$5$的后继状态有$0,1,2,3,4$,有$sg[5]=5$

当$M=6$时，$6$的后继状态有$1,2,3,4,5$有$sg[6]=mex\{sg[1],sg[2]……sg[5]\}=0$

当$M=7$时，$7$的后继状态有$2,3,4,5,6$有$sg[7]=mex\{sg[2],sg[3],sg[4]……sg[6]\}=1$

如此一来规律就好明显的有木有><.

最后贴上AC代码：
#include <iostream>

#include <cstdio>

using namespace std;

int main() {

    int m,l,n,sg,cas;

    cin>>cas;

    while(cas--){

        sg = 0;

        cin>>n;

        while(n--) {

            cin>>m>>l;

            sg ^= m%(l+1);

        }

        if(!sg) puts("Yes");

        else puts("No");

    }

    return 0;

}

巴特西

HDU1851 A Simple Game

最新文章

热门文章