当前位置: 代码迷 >> 综合 >> Problem G. The Stones Game【取石子博弈 思维】
  详细解决方案

Problem G. The Stones Game【取石子博弈 思维】

热度:81   发布时间:2023-12-16 22:52:21.0

在这里插入图片描述


题意

  • 有n个石头,m个人,问第k个人有没有必胜的状态。m个人轮流取石子,一轮没取完第一个人接着取,直到石子没有了。

  • 每个人取石子有2个操作。

    1. 可以选择取一个石子或者不取(0 or 1);
    2. 如果前一个人(当然第一个人除外,因为他没有前人,嘻嘻。。)的第一次操作取了石子,那么当前这个人这次不能取,反之必须取。也就是说,如果前一个人没有取一个石子,那么当前这个人这次必须取1个石子+你第一次操作选择取or不取。
  • 问最后一个石子被取完的算赢。


题解

  • 模拟每个人的必胜状态的石子个数。第一个人肯定只能两种选择0 or 1,那么第二个人的必胜状态的石子个数就肯定是2.因为无论第一个人怎么取,取不完并且第二个人都能取完。
  • 然后总结前两个人分别最少,最多取多少石子,很容易看出来是1 or 2。如果前两个人只取了1个石子,那么第三个人当前操作肯定能取2个石子,如果前两个拿了2个石子,那么第三个人也能拿一个石子,所以必胜状态是3.
  • 第四个人满足前面的状态是。前三个人最少,最大,分别能取2个,3个。第四个人想赢就肯定是得4个石子。如果前三个人取2个石子的话,1 2 3的取石子的状态分别是1 0 1或者0 1 1,所以第四个人都可以拿到2个,完成双杀。
  • 以此类推。推到这里我们就发现了规律,第K个人必胜的状态就是K个石子。 而且前N个人最多拿到的石子是N个。
  • 可得如果N>M的话,求余在与K比较即可。当然如果一开始N小于k的话,就直接可以GG了。

AC-Code

#include <bits/stdc++.h>
using namespace std;int main() {
    int T;	cin >> T;while (T--) {
    int N, M, X;	cin >> N >> M >> X;if (N < X) {
    cout << "NO" << endl;continue;}if (N % M == X || (N % M == 0 && M == X))	cout << "YES" << endl;else	cout << "NO" << endl;}return 0;
}
  相关解决方案