巴什博弈原理与证明

简介

巴什博弈的定义是:

有一堆物品,两人轮流取,每次可以取 \(1\) 到 \(m\) 个物品,最后把物品全部取完者胜利

现在给出初始的物品数 \(n\) 和 \(m\) ,判断先手是否有必胜策略

推理

\(m+1\mid n\) 时必败

巴什博弈的证明十分简单,用归纳法:

  • \(n\leq m+1\) 时

    若 \(n=m+1\) 那么先手取完后剩下的物品数范围是 \([1,m]\) ,后手可以直接取完胜利

    若 \(n\leq m\) 那么先手直接取完就能胜利

  • 若 \(n\leq k(m+1)\) 时命题成立

    那么 \(k(m+1)<n \leq (k+1)(m+1)\) 时

    若 \(n=(k+1)(m+1)\) 那么先手取完后剩下的物品数范围是 \([k(m+1)+1,k(m+1)+m]\) 后手可以正好取到 \(k(m+1)\) ,由假设得先手必败

    若 \(n<(k+1)(m+1)\) 那么先手可以取到 \(k(m+1)\) ,由假设得此时后手必败先手必胜

证毕

代码

HDU 1846

#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
    int t;
    scanf("%d", &t);
    while(t--) {
        ll n, m;
        scanf("%lld%lld", &n, &m);
        printf("%s\n", n % (m + 1) ? "first" : "second");
    }
    return 0;
}
上一篇:浅谈一类dp问题----状压dp


下一篇:Turtlebot 3 rplidar bringup