HDU 1517

原文

这是网上找的解题报告中思路很清晰的一个。显然这一题数字N到无穷大为必败态，之后从N开始往前溯，（N/9....N-1）为必胜态（在这个范围内的任意一个数可以转化为必败态区间的某一个数），(N/9/2,N/9-1)为必败态（在这个范围内的任意一个数只能转化为必胜态区间中的数），接下来继续按必胜->必负->必胜....这样循环就可以了，循环结束条件为区间是否将1包含进去即可（也就是左端小于等于1），循环时为区间添加个标记即可知跳出循环时是在必胜态还是必负态。

代码：

#include<iostream> #include<cmath> using namespace std; int main(){ double n; int flag; while(cin>>n) { flag=0; while(n>1) { if(!flag)//之前为必负态 n=ceil(n/9);//需要向上取整，否则可能到达不了必负态 else if(flag)//之前为必胜态 n=ceil(n/2); flag=!flag; } if(flag) cout<<"Stan wins."<<endl; else cout<<"Ollie wins."<<endl; } return 0; }