牛客国庆集训派对Day3 G（组合博弈）

链接：https://www.nowcoder.com/acm/contest/203/G

来源：牛客网

Stones

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 524288K，其他语言1048576K

64bit IO Format: %lld

题目描述

有n堆石子，第i堆石子有xi个。

修修和栋栋轮流取石子，每人每次需要从任意一堆石子中取走

个，修修先手。无法操作的人失败。此外，如果一个人取完了一堆石子，他会立即获胜。

不巧的是，修修除了数数以外啥都不会，他希望你帮他求出他能否获胜。

输入描述:

第一行一个整数t表示数据组数 (1 ≤ t ≤ 1000)。
每组数据第一行三个整数n,a,b (1 ≤ n ≤ 1000,1≤ a ≤ b ≤ 109)，第二行n个整数 (1 ≤ xi ≤ 109)。
      

输出描述:

每组数据输出一行一个字符串：如果修修可以获胜输出Yes，否则输出No。      

示例1

输入

复制

2
1 1 3
4
1 1 3
6      

输出

复制

No
Yes      

题意：如题

思路：

我的思考过程：

首先对于一堆石子x来说，可以找到它的必胜态和必败态：（类似巴什博奕可以算出）x%(a+b)∈[0,a)时，为先手比败态，其余为先手必胜态。到这边是对的，然后开始了我的崎岖的思考过程。。一开始我想两个人肯定是先去抢几个先手必胜的状态把它变为先手必败，那么就是如果先手必胜奇数个先手胜利，否则先手失败。后来发现有漏洞，必胜状态不一定是转换为必败态，也可以转换为必胜态，所以我就想将它转换为Nim博弈，太久没用SG函数，结果在这里又开始走弯路。。我想x%(a+b)最多通过几步可以转换为必败态，那么这一堆石头的个数就是这个数。。。

上面的问题在于Nim博弈中，一堆石子现在有n个那么[0,n-1]的状态它都可以达到，上面保证不了这一点。重新学习了一下SG函数。。挑选几个a，b的值，SG函数打个表找规律很快就可以发现规律。

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
int sg(int n,int a,int b)
{
    if(n<a)return 0;
    if(n<a+b)return 1;
    if(n%(a+b)<a)return 0;
    if(a==1)return n%(a+b)-a+1;
    if(n%(a+b)>=b)return 1;
    n+=a;
    return n%(a+b)/a;
}
int main()
{
    int t;
    int n,a,b;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d%d",&n,&a,&b);
        int x;
        bool first_win = false;
        int ans = 0;
        for(int i  = 0;i<n;i++)
        {
            scanf("%d",&x);
            if(x>=a&&x<=b)first_win = true;
            ans ^= sg(x,a,b);
        }
        if(ans==0&&first_win==false)
        {
            printf("No\n");
        }
        else 
        {
            printf("Yes\n");
        }
    }
}