牛客國慶集訓派對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");
        }
    }
}