SG定理：

根据Sprague-Grundy定理（SG定理），对于某些博弈论问题可以这样思考：

首先可以确定一个必败状态（记为P）或必胜状态（记为N）；

这样一来，若某一状态X若 可以 直接转移到P，则可以确定X为必胜状态；

若某一状态X 只能 转移到N，则可以确定X为必败状态。

以此通过递推可确定先手必胜或必败。

题一：hdu1404

代码：

#include
#include
#include
#include
#include
using namespace std;
const int maxn = 1e7+6;
bool sg[maxn];

int intlen(int x)
{
for (int i=6;i>0;i--)
{
int k=pow(10,(i-1));
if (x / k) return i;
}
}

void GetSG(int x)
{
//cout<<x<<endl;
int len=intlen(x);
for(int i=0; i<len; ++i)
{
int k=pow(10, i);
int q=x/k%10;
int y=x;
for(int j=q; j<9; ++j)
{
y+=k;
sg[y]=true;//可一步到达必败状态则为必胜
}
}
int y=x, k=1;
while(len<6)
{
y*=10;
for(int i=0; i<k; ++i)
sg[y+i]=true;
k*=10;
len++;
}
}

int main()
{
memset(sg, false, sizeof(sg));
sg[0]=true;
for(int i=1; i<1000000; ++i)
if(!sg[i])//必败则进入
GetSG(i);
char n[10];
while(gets(n))
{
if(n[0]=='0')
{
puts("Yes");
continue;
}
int m=atoi(n);
if(sg[m]) puts("Yes");
else puts("No");
}
return 0;
}

题二：hdu1404

代码：

#include
#include
#include
using namespace std;

int main()
{
long long n;
while(cin>>n)
{
int x=0;
for(; n>1; ++x)
{
if(x&1)
n = ceil(n*1.0/2);
else
n = ceil(n*1.0/9);
}
if(x&1) puts("Stan wins.");
else puts("Ollie wins.");
}
return 0;
}