題目鏈接：點擊查看

題目大意：給出k個黑球以及一個紅球，兩個人輪流摸球，摸到紅球算贏，問先手有優(yōu)勢還是后手有優(yōu)勢還是都一樣，若先手優(yōu)勢輸出1，若后手優(yōu)勢輸出2，若都一樣輸出0

題目分析：簡單博弈，我們只要將前幾種情況討論一下答案就出來了：

當(dāng)k=1時：很顯然贏和輸?shù)母怕识紴?/2，所以輸出0

當(dāng)k=2時：先手摸到黑球的概率為2/3，也就是說此時后手的局勢變?yōu)榱薻=1的情況，后手勝利的概率為2/3 * 1/2=1/3，所以先手勝利的概率為2/3，先手有優(yōu)勢，輸出1

當(dāng)k=3時：先手摸到黑球的概率為3/4，此時后手的局勢變?yōu)榱薻=2的情況，則后手勝利的概率為3/4 * 2/3=1/2，所以先手勝利的概率為1/2，所以輸出0

當(dāng)k=4時：先手摸到黑球的概率為4/5，此時后手的局勢變?yōu)榱薻=3的情況，則后手勝利的概率為4/5 * 1/2=2/5，所以先手勝利的概率為3/5，所以輸出1

當(dāng)k=5時：先手摸到黑球的概率為5/6，此時后手的局勢變?yōu)榱薻=4的情況，則后手勝利的概率為5/6 * 3/5=1/2，所以先手勝利的概率為1/2，所以輸出0

如此往復(fù)，我們可以發(fā)現(xiàn)進(jìn)入了一個循環(huán)，那么循環(huán)的關(guān)鍵就是k的奇偶，當(dāng)k為奇數(shù)時我們輸出0，當(dāng)k為偶數(shù)時我們輸出1即可

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const LL inf=0x3f3f3f3f3f3f3f3f;const int N=15;int main() { // freopen("input.txt","r",stdin);int n;while(scanf("%d",&n)!=EOF)printf("%d\n",n&1?0:1);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 5978 To begin or not to begin(简单博弈)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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