基础博弈论刷题题单

这里面收录了一些较为简单基础的博弈论题（HDU），之后的博弈论大概会单独出博客。

HDU1079 Calendar Game

题意：有一个起始年月日，每次可以月份加一或者日子加一，如果月份加一后不合法就只能日子加一（默认顺位），操作后超过终点算输，先到达2001年11月4日的胜。

发现操作会有奇偶性质的改变，终点状态是奇数，那么起始状态是偶数状态时必胜。考虑特殊日期，有两种，一种是闰年的2月29日和普通的2月28日；还有一种是连续两个大月导致的9月30日和11月30日向后的奇偶性质不变。第一种发现2月29日向后性质一致，必败；28日向后虽然是+1天必败，但是+1月可以避免，最优策略下必胜。第二种最优策略下向后+1天导致起始状态奇数必胜，特判。

read(Y),read(M),read(D);
puts(((!((M+D)&1))||(M==9&&D==30)||(M==11&&D==30))?"YES":"NO");

HDU1525 Euclid's Game

题意：给定两个数，每次可以用其中较大的数减去另一个数的整数倍（但不能小于0），先减为0的胜。

设n>m。

三种情况（先讨论初始状态）：

n==m 先手胜
n>=m*2 若(m,n%m)状态必败，那么先手必胜；否则先手可以选择(n%m+m,m)状态，此时后手只能选择必败状态。所以这时先手一定必胜。
m<n<m*2 只能选择(m,n%m)状态，反转胜负态即可。

while(read(n),read(m),n||m){
    int fp=1;
    while(1){
        if(n<m)swap(n,m);
        if(n==m||n>=m*2)break;
        n-=m,fp^=1;
    }
    puts(fp?"Stan wins":"Ollie wins");
}

HDU1564 Play a game

题意：给定一个nXn的棋盘，一棵棋子起始在(1,1),每次可以移动到纵向和横向任意一个未被访问过的点，最后不能移动的人数。

结论：n为偶数先手胜，n为奇数后手胜。

证明：

n为偶数的情况：初始剩下n*n-1个点，先手走完剩下n*n-2个点，此时一定能用若干个2X1的方块填满剩下的空位，所以每次后手走时一定能走2X1的另一格，后手必败。
n为奇数的情况：初始剩下n*n-1个点，先手走完剩下n*n-2个点，正好是后手的必胜态，即先手必败。

while(read(n),n){
    puts(n&1?"ailyanlu":"8600");
}

HDU1846 Brave Game

题意：n个石子，每次能从中拿1~m个，最后不能拿的输。

巴什博弈的模板题。

先考虑一个特殊情况，n=m+1时，无论先手怎么拿，后手一定赢，所以这是个必败态。容易推论出n=k*(m+1)也同样是必败态。

再考虑所有的情况，n可以表示为k*m+b。当b不等于0时，先手只需要拿走b个即可让后手进入必败态，此时先手必胜。

read(n),read(m);
puts(n%(m+1)?"first":"second");

HDU3032 Nim or not Nim?

题意：每次可以选择从一堆中拿若干个石子，也可以选择将当前堆分为两堆，拿完最后一个的人赢。

将小范围的SG函数打表可得：

x==0 ：SG(x)=0
x==k*4 : SG(x)=x-1
x==k*4+3 : SG(x)=x+1
其他情况 : SG(x)=x

int SG(int x){
    if(x==0)return x;
    if(x%4==3)return x+1;
    if(x%4==0)return x-1;
    return x;
}

read(n);
int Ans=0;
for(int i=1,x;i<=n;++i){
    read(x),Ans^=SG(x);
}
puts(Ans?"Alice":"Bob");

HDU3389 Game

题意：给定n个盒子，每个盒子中有若干数量的一模一样的卡片，每次可以选择满足条件的A（非空）和B（B<A,(A+B)%2==1,(A+B)%3==0），然后从A移动非零数量的卡片到B中，最后无法移动的输。问胜负情况。

阶梯博弈。

首先确定了编号为1/3/4的盒子无法移动，是终点状态。

容易找到规律，编号Mod 6等于0/2/5的盒子走奇数步到终点状态，其他盒子为偶数步。

奇数步的盒子看作Nim游戏即可。（阶梯博弈）

read(n);
int Ans=0;
for(int i=1,x;i<=n;++i){
    read(x);
    if(i%6==0 || i%6==2 || i%6==5){
        Ans^=x;
    }
}
printf("Case %d: %s\n",_T,Ans?"Alice":"Bob");

HDU3951 Coin Game

题意：给定n个围成环的硬币，每次可以选择取出连续的1~k个硬币，取走最后一个硬币的胜。问胜负情况。

分类讨论：

n<=k ：先手取走所有硬币，必胜。
n>k : 先手取走若干硬币后，环变为链。
- k>1 ：后手一定能取走若干硬币使得链划分为两条等长的链，此时后手只需要模仿先手取法即可必胜。
- k==1: 判断n的奇偶性确定胜负。

read(n),read(k);
printf("Case %d: ",++Cnt);
if(n<=k)puts("first");
else if(k>1)puts("second");
else puts(n&1?"first":"second");