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

· · 题解

首先，合并次数为奇数先手必胜，偶数后手必胜，那么两个人都会尽可能向着自己想要的方向去发展(即拉到总合并次数为奇数/偶数)

具体实现方式：

当n ≤ m时，这种情况最后肯定能合成一堆，我们称这个较大的堆为【大堆】。
假如现在轮到先手操作，先手还没动，这个时候最长合并次数为偶数次，那么先手有两种可能性，把后面一个堆丢进大堆里面，这样后手再丢一个小堆进去，或者把后面两个堆合成一个，那么后手就可以把这个合成的直接丢进去。
无论怎么做，后手都能保证每轮完了之后，大堆的石子会增加两个，那么合并次数也会-2，一直保持为偶数。直到最后先手合无可合。

因此就可以保证剩下的合并次数为原始奇/偶，同时这种方式也会把局数拉到最多。

想办法弄到对自己有利

如果拉到最长的操作次数我们必胜的话，那么不管对面怎么操作，我们都能用上述方法拉回来

同样如果最长的操作是对面必胜，不管我们怎么合并，对面也能用上述方法拉回来

以及

我们已经发现最长的情况我们必胜，无论对手怎么操作我们都能拖到最长，我们必胜

对手发现最长他必胜，无论我们怎么操作，他也肯定能往下拖。

所以对最长必胜的那一方来说，一直拖到最长就是最优策略

而我们已经分析了必胜的那一方总是能拖下去

即这是一种必然取胜的方法，且如果对手不按套路出牌我们也能拖回来。

因此最终答案就是最长能拖到的次数，如果为奇先手胜，如果为偶后手胜。

最长次数

在n<=m的情况下可以轻松判断出是n-1；

若n>m，则最后最大合并后堆数一定是{m,m,m,m,n%m}; （因为如果是形如{m,m,m,m-x,m-x}的形式，不好算，我觉得其实是没什么不一样的Orz，可能仅仅只是不好算吧Orz）

因此ans=(n/m)*(m-1)+n%m?n%m-1:0;

代码

#include<cstdio>
#include<iostream>
using namespace std;
int T;
long long int n,m;
int main()
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
    {
        scanf("%lld%lld",&n,&m);
        long long int ans=(n/m)*(m-1)+((n%m)?(n%m-1):0);
        if(ans&1) printf("0\n");
        else printf("1\n");
    }
    return 0;
}

向管理员道歉Orz，手滑交成题解了，不要管我Orz