當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

HDU-2149(博弈)

發布時間：2025/3/21 编程问答 7 豆豆

生活随笔收集整理的這篇文章主要介紹了 HDU-2149(博弈) 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=2149；

Public Sale

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 11335????Accepted Submission(s): 6708

?

Problem Description

雖然不想，但是現實總歸是現實，Lele始終沒有逃過退學的命運，因為他沒有拿到獎學金。現在等待他的，就是像FarmJohn一樣的農田生涯。

要種田得有田才行，Lele聽說街上正在舉行一場別開生面的拍賣會，拍賣的物品正好就是一塊20畝的田地。于是，Lele帶上他的全部積蓄，沖往拍賣會。

后來發現，整個拍賣會只有Lele和他的死對頭Yueyue。

通過打聽，Lele知道這場拍賣的規則是這樣的：剛開始底價為0，兩個人輪流開始加價，不過每次加價的幅度要在1～N之間，當價格大于或等于田地的成本價 M 時，主辦方就把這塊田地賣給這次叫價的人。

Lele和Yueyue雖然考試不行，但是對拍賣卻十分精通，而且他們兩個人都十分想得到這塊田地。所以他們每次都是選對自己最有利的方式進行加價。

由于Lele字典序比Yueyue靠前，所以每次都是由Lele先開始加價，請問，第一次加價的時候，
Lele要出多少才能保證自己買得到這塊地呢？

Input

本題目包含多組測試，請處理到文件結束(EOF)。每組測試占一行。
每組測試包含兩個整數M和N(含義見題目描述，0<N，M<1100)

Output

對于每組數據，在一行里按遞增的順序輸出Lele第一次可以加的價。兩個數據之間用空格隔開。
如果Lele在第一次無論如何出價都無法買到這塊土地，就輸出"none"。

Sample Input

4 2

3 2

3 5

Sample Output

none

3 4 5

題目大意：給你一個成本價為M, 然后兩個人按順序叫價，但每次叫價增加的價格必須在（1~N）之間，最后誰報的的價先超過或等于M,誰就贏。兩個人都很聰明，主角先叫價，問他第一次報價為多少時可以贏，如果能贏把他第一次報價的所有能贏的價格都輸出來，如果沒有贏的可能性就輸出none。

解題思路：典型的博弈，如果對博弈一點都不了解，只是單純找規律，做起來會很惱火。這道題就是巴什博奕，就相當于有M個物品，兩個人輪流取，每次只能去（1~n）個。誰能先取完，誰就贏。這里有個公式M=（n+1）r+s,只要第一個人能取走s個，后手無論怎么取，比如k個（k<n）。那么先手只需要去（n+1-k）個。這樣下去先手一定是第一個取完M的，這就是先手必勝，反之如果M與n+1取余為0，先手必敗。這道題稍微又多了一點變化，n可以大于M,這種情況需要特判一下，這也是先手必勝的情況只需要輸出（M~N）就行了。輸出所有能贏的價格就是保證你第一次報價后剩下的價格必須保證是（n+1）的倍數，就ok了，就這一點變化。

AC代碼：

#include<cstdio> int main() {int m, n;while(~scanf("%d%d", &m, &n)) {if(m <= n){printf("%d", m);for(int i = m + 1; i <= n; ++i){printf(" %d", i);}printf("\n");continue;}int r = m % (n + 1);if(r == 0){printf("none\n");}else{int x = 0;for(int i = 1; i <= n; i++){if((m - i) % (n + 1) == 0){if(x == 0)printf("%d", i);elseprintf(" %d", i);x++;}}printf("\n");}}return 0; }

總結

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

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