POJ 2348 Euclid's Game（辗转相除博弈+自由度分析）

题目链接：http://poj.org/problem?id=2348

题目大意：给你两个数a,b,Stan和Ollie轮流操作，每次可以将较大的数减去较小的数的整数倍，相减后结果不能小于0，谁先将其中一个数字变成0谁就获胜。

解题思路：看了挑战程序设计上的，这里我们先假设a<b，当b是a的整数倍是必胜态。我们讨论以下b不是a的整数倍，此时a,b的关系按照自由度的观点（第一次听说），可以分为以下两种情况：

　　　　　①b-a<a

　　　　　②b-a>a

那么对于①，玩家只有从b中减去a这一个选择。如果b-a得到的状态是必败态，那当前就是必胜态，反之，就是必败态。例如从（4,7）出发，只有（4,7）->（4,3）->（1,3）这一条路，（4,7）是必胜态。

但是对于②，有从b中减去a,2a或者更高的倍数等多种选择。假设x是使得b-a*x<a，我们考虑一下两种情况：

　　　　1）将b-a*(x-1)，得到状态①。

　　　　2）将b-a*x，不能确定是状态①还是②。

并且我们可以发现，b-a*x是b-a*(x-1)唯一能转移到的状态，如果b-a*(x-1)是必胜态，那就执行b-a*(x-1)，但如果是必败态呢，那b-a*x是就是必胜态。所以无论如何只要到了状态②就肯定会赢。

所以我们得到了结论：从初始状态开始最先到达自由度的第二种状态或者得到b是a的整数倍的一方必胜。

代码：

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 int main(){

     int a,b;

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

         int cnt=;

         while(){

             cnt++;

             if(a>b)

                 swap(a,b);

             if(b%a==)

                 break;

             if(b-a>a)

                 break;

             b-=a;

         }

         if(cnt&)    puts("Stan wins");

         else    puts("Ollie wins");

     }

 }

巴特西

POJ 2348 Euclid's Game（辗转相除博弈+自由度分析）

最新文章

热门文章