题解 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; #### 代码 ```cpp #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