欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-06-26 10:12:51
...

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


题意

  • 有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;
}