HDU 2149 – Public Sale [巴什博弈]

vjudge题目链接

中文题目,不再介绍题意。可以转化为巴什博弈,即对一堆m个的石子,两个人轮流取石子,每次取1~n个石子,两人均采取最佳策略,最先取完的人获胜,问第一个取石子的人能否获胜,或者问最终谁会获胜。

本题当m % (n + 1) == 0的时候先加价的人无法获胜,其余情况可以获胜。如果刚开始可以一次加价够数(n<=m),那么就有多种加价方法,即m~n。如果第一次无法加价满,那么可以使得每次加价完后剩余m+1的倍数,这样最后无论第二个人怎样去加价,第一个人都会获胜。

 

#include <cstdio>
using namespace std;

int main() {
    int m, n;
    while(~scanf("%d%d", &m, &n)) {
        if(m % (n + 1) == 0) puts("none");
        else if(m <= n) {
            for(int i = m; i <= n; ++i)
                printf("%d%c", i, i==n ? '\n' : ' ');
        }
        else printf("%d\n", m % (n + 1));
    }
    return 0;
}

欢迎留言