題目鏈接：點擊查看

題目大意：給出初始的兩個數(shù)字，每一次操作都要在規(guī)則下進行：令較大的數(shù)減去任意倍較小的數(shù)，必須保證不能出現(xiàn)負數(shù)，先減到零者獲勝，問誰能獲勝

題目分析：這個題目說是博弈我感覺更像是找規(guī)律，我們來分析一下這個題目

首先我們設（a,b）中b永遠比a大，那么分為兩種情況：

當a<b&&2*a>b時，只能進行一種操作，即b-=a，模擬即可

當a<b&&2*a<b時，b有至少一種操作可以選擇了，我們設此時b最多可以減去x倍的a，那么我們不妨先令b減去(x-1)倍的a：

在b減去(x-1)倍的a之后，因為此后的b仍然大于a，所以接下來的操作必然只有再讓b減去a這一種操作，就回到了第一種討論的情況之中，如果當前情況為必敗狀態(tài)的話，那么原狀態(tài)(a,b)就是必勝態(tài)

接上條所述，若在b減去(x-1)倍的a之后，當前狀態(tài)變?yōu)榱吮貏贍顟B(tài)的話，那么就意味著一開始b減去x倍的a是必敗狀態(tài)，那么我們大可在一開始就減去x倍的a即可

綜上所述，我們可以模擬整個過程，直到出現(xiàn)了結果，或者出現(xiàn)了b>2*a的狀態(tài)就可以停止了，若b>2*a之后，先手就可以操控整個游戲的局面了，所以此時肯定是先手必勝

代碼：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e5+100;int main() { // freopen("input.txt","r",stdin);int a,b;while(scanf("%d%d",&a,&b)!=EOF&&a+b){int ans=0;while(1){if(a>b)//保證b>aswap(a,b);if(b%a==0||b-a>a)break;b-=a;ans^=1;if(a>b)swap(a,b);}if(ans)printf("Ollie wins\n");elseprintf("Stan wins\n");} return 0; }

?

總結

以上是生活随笔為你收集整理的POJ - 2348 Euclid's Game(博弈)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。