牛客国庆集训派对Day3G Stones
G Stones
原博客地址
https://blog.csdn.net/weixin_39792252/article/details/81448795
博弈问题
终止条件
- 某一个人不能再拿
- 某一个人取完了一堆石子
首先考虑的就是如果有石子的堆数量在a,b之间，那么直接取完这一堆直接结束游戏了，在计算grundy值 的时候也不会出现a,b的grundy值(不会留给对手必胜的机会)
打表grundy值，发现规律，循环节是a+b，grundy(i) = i%(a+b）/a;
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+7;
ll x[maxn], a, b, n;
int SG[maxn],S[maxn];
ll check(ll m) {
m %= (a+b);
m /= a;
if(m == 0) return 1;
else if(m == 1) return 0;
else return m;
}
int main()
{
//printf("a , b : %d %d\n", 2, 5);
//getSG(100, 1, 6);
//cout<<endl;
int t; scanf("%d", &t);
while(t--)
{
scanf("%lld%lld%lld", &n, &a, &b);
for(int i = 0; i < n; i++) scanf("%lld", &x[i]);
bool f = false;
ll res = 0;
for(int i = 0; i < n; i++) if(x[i]>=a&&x[i]<=b) { f = true; break; }
if(f) { puts("Yes"); continue; }
if(a == 1) for(int i = 0; i < n; i++) res ^= ((x[i] - b - 1)%(a+b));
else for(int i = 0; i < n; i++)
if(x[i] > b) res ^= check(x[i] - b);
if(res == 0) puts("No");
else puts("Yes");
}
}
