首页 > 代码库 > HDU1851 A Simple Game

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