HDU 1729 Stone Game (SG函数)

给出一些盒子，盒子有容量限制，有初始容量，每次给某一个盒子中添加石头。
添加的数量必须小于等于盒子中已有数量的平方。
感觉上有一点像 Wythoff Game。当然肯定比那个复杂
对于上限为S,当前容量如果为C,如果C+C*C<S&&(C+1)+(C+1)*(C+1)>=S，那么对于（S,C）显然是一个必败态
因为你不管一次取多少，不可能直接获胜，而对方都能直接获胜。
那么就继续递归求C状态。
如果最大的必败T>当前的C，那么就求出C后继中最小，也就是S-C
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cmath> 
#include<algorithm> 
#define N 10005 
#define LL long long 
#define inf 1<<29 
#define eps 1e-7 
using namespace std; 
int get_sg(int s,int c){ 
    int q=sqrt((double)s); 
    while(q+q*q>=s) 
        q--; 
    if(c>q) return s-c; 
    else return get_sg(q,c); 
} 
int main(){ 
    int n,cas=0; 
    while(scanf("%d",&n)!=EOF&&n){ 
        int s,c; 
        printf("Case %d:\n",++cas); 
        int ans=0; 
        while(n--){ 
            scanf("%d%d",&s,&c); 
            ans^=get_sg(s,c); 
        } 
        if(ans) 
            puts("Yes"); 
        else 
            puts("No"); 
    } 
    return 0; 
} 
作者;ACM_cxlove

补充：软件开发 , C++ ,