本文主要是介绍P4101 人人尽说江南好，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接:P4101 人人尽说江南好
算法分析
无论怎么操作，最终合并的次数为奇数，则先手胜，否则先手败。先假设一种合并方案，双方尽量合并成 m m m，然后再从1开始合并。这样总共的合并次数为： c n t = n / m ∗ ( m − 1 ) + （ ( n % m ) ? ( n % m − 1 ) : 0 ） cnt = n/m*(m-1)+（(n \% m)?(n\% m-1):0） cnt=n/m∗(m−1)+（(n%m)?(n%m−1):0）。我们称此为套路。
如果此时cnt为奇数，我们知道先手胜。先手必胜，肯定会按照套路走，如果后手不按照套路出牌呢？讨论下：
最大堆石子数 < = m − 2 <=m-2 <=m−2
-
后手将1和最大堆合并，这是按照套路走的，先手继续按照套路走即可。
-
后手将两个1合并，得到一个为2的堆，先手将这个为2的堆和最大堆合并，将后手的思路拉回到套路上来。
最大堆石子数等于 m − 1 m-1 m−1
-
后手将1和最大堆合并，没有区别。
-
后手合并两个1，得到一个为2的堆，先手将1合并到最大堆，此时最大堆已满。后面又可以按照套路来了。
无论怎么操作，先手都可以稳住套路，保证最后的合并次数不变。
后手胜的情况也是一样的。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define ll long long
ll n, m, cnt;
int main()
{int T;scanf("%d", &T);while (T--){scanf("%lld%lld", &n, &m);cnt = n / m * (m - 1) + ((n % m) ? (n % m - 1) : 0); // ?:运算符得用括号，否则错 if (cnt & 1) printf("0\n"); else printf("1\n");}return 0;
}
反思与总结
-
在用条件运算符时，整体得加括号，否则错误。
-
该题思路：确定一种方案，证明其他方案最终和该方案等效。
这篇关于P4101 人人尽说江南好的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
