首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。