hdoj 1729 Stone Games（SG函数）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1729

看了题目感觉像Nim，但是有范围限制，有点不知道SG函数该怎么写

看了题解，最后才明白该怎么去理解。

首先进行对s和c进行分类，

1、c = 0 的时候，无论怎样都填不满，直接跳过；

2、c = s 的时候，先手必败，即是P态；

3、c < s 的时候，可以分为两种情况：

1）c^2 + c < s 的时候，递归

2）c^2 + c > s 的时候，先手必胜，即N态

 int mex(int s, int c){
      || s == c)
         ;
     int q = sqrt(s);
     while( q+q*q >= s)
         q--;//最大的不能一次填满的数
     if(c > q) return s-c;
     else return mex(q,c);
 }

主要的理解难点就是 mex(s,c)和mex(k,c)为什么是等价的，个人是这么理解的，

当跑到第一个q+q*q<s的时候，如果c>q，那么可以一次填满，

但如果c<q，不可能一次填满，此时可以分割成两个事件，mex(c,k)和mex(s,k)，

其中对于mex(s,k),mex(s,s) 是先手必败，即P态，mex(s,k+1)...mex(s,s-1)都是先手必胜，即N态，

所有移动都导致N态局面的是P态，所以显然mex(s,k)是P态，那么mex(s,k)显然与mex(k,c)等价

 #include<stdio.h>
 #include<cmath>
 #include<cstring>
 using namespace std;
 ;
 int mex(int s, int c){
      || s == c)
         ;
     int q = sqrt(s);
     while( q+q*q >= s)
         q--;//最大的不能一次填满的数
     if(c > q) return s-c;
     else return mex(q,c);
 }
 int main(){
     int N;
     int ans;
     int s, c;
     ;
     while(~scanf("%d",&N)&&N){
         ans  = ;
         ; i < N; ++i){
             scanf("%d%d",&s,&c);
             ans = ans^mex(s,c);
         }
         printf("Case %d:\n",++T);
         if(ans)
             puts("Yes");
         else
             puts("No");
     }
 }

巴特西

hdoj 1729 Stone Games（SG函数）

最新文章

热门文章