题解 P4101 【[HEOI2014]人人尽说江南好 】

· · 题解

\Large\color{#FFBBFF}\textit{Tian-Xing's blog}

Description

传送门

Solution

如果每个人每次都只是将一个大小为1的石子堆放到当前最大的石子堆里，那么当游戏不能玩的时候局面必定是有n / m个大小为m的石子堆和\left [ n \mod m \neq 0 \right ]个大小为n \mod m的石子堆。

一共需要\left ( m - 1 \right ) \times \left (n / m \right ) + \left[ n \mod m \neq 0 \right ] \times \left ( n \mod m - 1 \right )步达到最后的局面。

如果都按照这样的策略进行游戏，那么如果步数是奇数就是先手胜否则是后手胜利。但是现在还有别的决策可以执行，而且最终局面不是唯一的，但是可以采用一种策略使最终局面就是这样的。考虑如果按这个策略进行游戏本来是先手必胜那么当后手执行决策时有两种可能。

第一种将一个大小为1的石子堆和最大的石子堆合并，这样先手只要继续执行策略最后就能获胜。

第二种将两个大小为1的石子堆合并，这样先手下次只要将这个大小为2的石子堆和最大的合并就行，和上面的第一种情况一样都是得到一个最大的石子堆和一些大小为1的石子堆。

如果不能合就直接拿一个大小为1的石子堆和最大的合并就行，和上面第一种情况得到的局面还是一样的，都是一个大小为m的石子堆和一个大小为2的石子堆还有一些大小为1的石子堆。

所以无论是那种决策达到最终局面的步数不变，依然是先手必胜。如果一开始算的步数是后手必胜同理。

所以按这种决策计算的步数是奇数就是先手胜否则就是后手胜。

Code

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int n, m;

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        scanf("%d%d", &n, &m);
        printf("%d\n", (n - (n / m) + (n % m != 0)) % 2 == 0 ? 1 : 0);
    }
    return 0;
}