(博弈论)hdoj 1525 Euclid's Game

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1525

题目大意:Stan和Ollie在玩一个游戏,a和b两个数字,每次可以选择较大的数减去较小的数的若干倍,最后将大数减为0的人获胜。问给定的两个数字,谁会获胜。

  后来的思路最后必然的局面是b,a%b,如果a>=b&&a<2*b,那么只有一种情况,直接到b,a%b。否则有多种情况。而a/b>=2的话,先手可以选择由谁面对b,a%b这样的局势,每一次的选择也可以决定后一次的抉择由谁进行选择,先手一直掌握先手优势,所以第一个获得先手优势的人必胜。

     #include<stdio.h>
     #include<algorithm>
     using namespace std;
     int main()
     {
         int flag;
         int a, b;
         int c;
         int cnt;
         while(~scanf("%d%d",&a,&b)){
              && b== )
                 break;
             if( a < b )
                 swap(a,b);//此时a>b
             flag = ;
             cnt = ;//cnt为偶数表示是S的操作回合
             ){
                  && cnt %  ==  ){
                     flag = ;
                     break;
                 }
                  && cnt %  ==  ){
                     flag = ;
                     break;
                 }
                 c = a % b;
                 a = b;
                 b = c;
                 cnt ++;
 //                printf("%d %d \n",a,b);
             }
              ==  && flag ==  ) || flag ==  )
                 puts("Stan wins");
              ==  && flag ==  ) || flag ==  )
                 puts("Ollie wins");
         }
     }
上一篇:PAT——乙级真题1002代码


下一篇:java 学习心得