HDU 1525 Euclid Game

题目大意：

给定2个数a ， b，假定b>=a总是从b中取走一个a的整数倍，也就是让 b-k*a(k*a<=b)

每人执行一步这个操作，最后得到0的人胜利结束游戏

（0，a)是一个终止态P（必胜态）

始终假设b>=a

那么（a，b）b%a==0 ，那么就是必败态 N

如果2*a>b>a 那么只能选择进入 (a , b-a)不确定什么状态

因为每个人都很聪明，所以对于碰到一个a ，b的局面

如果 b>a*2 ，那么应该知道 (a , b%a) 是不是一个必胜态，如果不是，那么这个聪明人就总会进入(a , b%a+a) ,就能逼迫对方进入 (a , b%a) 这个必败态

如果 (a , b%a) 是一个必胜态，那么聪明人就会自己进入这个状态

所以 b>2*a的时候，下个人肯定是必胜的，也就是下个人必然进入必胜态，所以这是一个必败态

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 bool dfs(int a , int b)

 {

     if(a>b) swap(a , b);

     if(a == ) return true;

     if(b%a ==  || b > *a) return false;

     bool flag1 = dfs(a , b%a);

     bool flag2 = false;

     if(b > *a) flag2 = dfs(a , b%a+a);

     if(flag1 || flag2) return false;

     return true;

 }

 int main()

 {

    // freopen("a.in" , "r" , stdin);

     int a,b;

     while(scanf("%d%d" , &a , &b) , a||b)

     {

         if(dfs(a , b)) puts("Ollie wins");

         else puts("Stan wins");

     }

     return ;

 }

巴特西

HDU 1525 Euclid Game

最新文章

热门文章