hdu 1729 sg博弈

做过的第一题真正意思上的sg博弈。然后各种不会。

http://acm.hdu.edu.cn/showproblem.php?pid=1729

转载出处：http://qianmacao.blog.163.com/blog/static/2033971802012343334856/

博弈SG函数问题、寻找必败态

题目大意：（取石子游戏）有n个箱子，体积为Si，当前箱子里的石子数为Ci。两个人轮流往箱子里放石子，而且每一次放是数量都有限制，不能超过当前箱子内石子数的平方。例如箱子里有3颗石子，那么下一个人就可以放1~9颗石子，直到箱子被装满。当有一方放不下石子时游戏结束，最后放不下石子的人输。

算法分析：

PS：SG(X)=mex(SG(X->Y1),SG(X->Y2),SG(X->Y3),...........,SG(X->YN));是y1 ,y2 ,y3......的SG值取mex；而不是对（Y1，Y2，...YN）取mex;

http://blog.163.com/scuqifuguang@126/blog/static/171370086201101711276278/这个文章很不错。

那么对于这题对于每一堆，放石子放满就想当于满的时候取s-c个，反向只是让我理解题意更深。

首先我们知道（S，S）这个局面是必败局面。

对于每一堆能加的数量有限，而当c的值（大于或者等于）D=sqrt(s) 或者 D=sqri（s）+1的时候就可以一次完成，就是说可以从当前局面到达（S，S）的局面，所以当前局面是必胜局面。

而这种情况下，你能造成的局面有集合A={0,1,2,...,s-c-1}；因为你可以去s-c，s-c-1，s-c-2，.....，1；那么对应mex(x)函数（即A中未出现的最小的一个数字），那么自然该局面的SG值就是s-c了；

另外当c的值小于D的时候，是不可能一下子加满的，因为c*c+c绝对是小于s的；那么小于D的局面一定能够是必输的吗？很显然不是的。

对于（S，D-1）这个局面，一定是必输，因为他能到的局面都是必胜！现在c小于D，那么如果（S，C）这个局面能到（S，D）；就代表这个局面是必胜的。所以现在SG值要在新集合（D，C）中求，而求法与上面的相同求新的D，所以可以用递归函数：当C>D时，返回（S-C）

差不多就是这样。

其实D = sqrt(s);这里算是个加速，要不然就要：while(d*d+d < S) d++;这样会很慢的。

思路：这题明显的sg函数。可惜我纠结了半天没想起思路来。设当前的箱子容量为si，求出一个t满足：t + t * t < si，若是当前箱子里有ci颗石头，

1、ci > t 则必胜；

2、ci == t 则必败；

3、ci < t不可立即断定，将t作为si递归调用函数。

当满足ci > t时，return si - ci 作为当前状况的sg值。因为：

如图：

HDU 1729 Stone Game - _眼淚笑了 - _眼淚笑了

当ci在si点时，为有向图的端点，出度为0，也就是必败点，所以sg值为0；

当ci 位于si - 1时，ci的端点可能的sg值构成的凑集为{0}，所以当前sg值为1；

当ci 位于si - 2 时，ci的端点可能的sg值构成的凑集为{0， 1}，所以当前的sg值为2；

可得，ci地点地位的sg值为si - ci；

View Code

// I'm lanjiangzhou
//C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <time.h>
//C++
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cctype>
#include <stack>
#include <string>
#include <list>
#include <queue>
#include <map>
#include <vector>
#include <deque>
#include <set>
using namespace std;

//*************************OUTPUT*************************
#ifdef WIN32
#define INT64 "%I64d"
#define UINT64 "%I64u"
#else
#define INT64 "%lld"
#define UINT64 "%llu"
#endif

//**************************CONSTANT***********************
#define INF 0x3f3f3f3f

// aply for the memory of the stack
//#pragma comment (linker, "/STACK:1024000000,1024000000")
//end

const int maxn = 1000000+100;
int sg[maxn];

int mex(int s,int c){
    int t=(int)sqrt((double)s);
    while(t+t*t>=s) t--;  //找到符合条件的点
    if(t<c) //找到大于c的最下必败点
        return s-c;
    else
        return mex(t,c);
}

int main(){
    int n;
    int kases=0;
    while(scanf("%d",&n)!=EOF){
        if(n==0) break;
        int s,c;
        int m=0;
        for(int i=0;i<n;i++){
            scanf("%d%d",&s,&c);
            m^=mex(s,c);
        }
        printf("Case %d:\n",++kases);
        if(m==0) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}