题目描述

给定n堆石子以及一个由k个不同正整数构成的数字集合S。

现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合S，最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

数据范围

1≤n,k≤100,
1≤si,hi≤10000

样例

2
2 5
3
2 4 7

输出

Yes

定理1：对于集合S,mex(S)=mex({x1,x2…})=S中 没有出现的 最小非负整数
定理2.1：sg(n)=mex({sg(i1),sg(i2),sg(i3)....})。 n为结点；i1,i2,i3…是n的后继结点
定理2.2：sg(G)=sg(head). G是一个有向图,head是G的头结点。
定理3：sg(G1)^sg(G2)^sg(G3)^…^sg(Gn)为n个有向图的异或和,对于n个有向图游戏,这个异或和就是它的答案（和nim类似，这个定理感兴趣可以去证明）

算法1:递归

C++ 代码

#include <bits/stdc++.h>
using namespace std;
#define LL long long
int s[110], k, l, x, sg[11000], ans;
//这个题目的有向图可以看成一个树,叶子结点就是必败结点值为0。非叶子结点存放mex({子节点的值})。
int sg_dfs(int n)
{
    bool mex[110]; //对于每个结点n都开一个数组mex 记录他的后继结点
    memset(mex, 0, sizeof(mex));
    if (sg[n] != -1)
        return sg[n];
    if (n - s[0] < 0) //最小的都不可以取,这个n没有后继了,数组中标记为0.
        return sg[n] = 0;
    for (int i = 0; i < k && (n >= s[i]); i++) 
        mex[sg_dfs(n - s[i])] = 1;             //n的后继标记为1
    for (int i = 0;; i++)
        if (!mex[i]) //mex集合中！没！出现过的最小的非负整数
            return sg[n] = i;
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> k;
    memset(sg, -1, sizeof(sg));
    sg[0] = 0;
    for (int i = 0; i < k; i++)
        cin >> s[i]; //s集合的值（每一步可以取得数）
    sort(s, s + k);

    cin >> l; //l堆
    ans = 0;
    for (int i = 0; i < l; i++)
    {
        cin >> x;
        ans ^= sg_dfs(x); //将每个堆当成一个有向图 最终答案为sg(x)异或和
    }
    if (ans)
        cout << "Yes\n";
    else
        cout << "No\n";

    return 0;
}

算法2 非递归

道理一样，写法不同，先初始化了sg数组。

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int SG[N], k, m, x, l, ans;
int a[110];
//返回集合s中的最小非负整数
int mex(int s[], int n)
{
    if (n == 0)
        return 0; //没有后继
    sort(s, s + n);
    n = unique(s, s + n) - s;
    for (int i = 0;; i++)
        if (i >= n || s[i] != i)
            return i;
}
//eg:x的后继为x-a[0],x-a[1],,,,,x-a[n-1];
int sg(int x)
{
    int cnt = 0;
    int b[N];
    for (int i = 0; i < k; i++)
        if (x >= a[i])
            b[cnt++] = SG[x - a[i]];
    return mex(b, cnt);
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> k;
    for (int i = 0; i < k; i++)
        cin >> a[i]; //s集合的值（每一步可以取得数）
    sort(a, a + k);
    for (int i = 1; i < N; i++)
        SG[i] = sg(i);

    cin >> l; //l堆
    ans = 0;
    for (int i = 0; i < l; i++)
    {
        cin >> x;
        ans ^= SG[x]; //将每个堆当成一个有向图 最终答案为sg(x)异或和
    }
     if (ans)
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}