这个解析的前提是 从这些堆里拿 从外界放出去 例如 10个堆 从堆1 拿出来100 个 然后从外界放入99 98个 总数多了97个

是的

A佬提的全局变量的这个点挺有意思，对比之前的集合-Nim，想了一下，可以从这个角度来解释为什么前者不可以将S作为全局变量，而后者可以
对于集合-Nim，注意到0这个值可以被映射多次（可以参考该题解下前面几位小伙伴画的图），这意味着有多个可能的值xi作为叶子节点（末尾节点），满足f[xi] = 0。而如果将S作为全局变量，则其中只能有一个值x’映射到0，其他的值都将映射到大于0的值（即f[x'] = 0，f[xi/x'] > 0，xi/x'代表集合x排除掉x’所剩值组成的集合），因而不能将S作为全局变量。
而对于该题，注意到0总是只能由0映射得到（即f[0] = 0），并且除了叶子节点之外的其他节点的映射都满足一一映射条件（该条件事实上对于集合-Nim也成立），所以将S作为全局变量是可行的。

说的太对了

题目含义：将一堆石子（比如100个）拿走，然后建立全新的两个堆，这两个堆石子分别要小于100个（0-99），两个堆的和没有要求（最大99+99），由于保证每次分下来，新堆（2个堆分别）的石子数是小于旧堆的，最后一直分堆，全是1，然后拿走1，建立2个石子为0的堆，一直拿走1个石子，最后导致无法操作

这里为啥unordered_set定义为全局变量

这个无所谓吧

for(int i=0;i<x;i)
for(int j=0;j<=i;j)
S.insert(sg(i)^sg(j));
为啥i+j的值可以大于x？ sg()sg() 括号里面的值是分配之后堆的数还是要分配到这两个堆的石子数？

每一堆可以变成小于原来那堆的任意大小的两堆，建议再审一下题，或者评论区里再看看

可是为什么不考虑比如 100 99 98 这样的话，会出现199 98 0 这种情况呀。而代码不包含这种情况

不会出现199的，拆分之后并不会合并

只能拆分之后放入空堆吗？

感觉精髓就在这，题目里要求合并堆，但其实 $SG$ 函数和节点数无关，只和 当前有向图图所有点的$SG$函数异或结果有关

嗯嗯，只管处理前就好，处理后的情况还要再讨论或者打表

感觉加粗文字那里表述有点问题。一堆石子数为$a[i]$，那么将其拆分成$b[i]和$b[j]$,如果令$b[i] = a[i]，b[j] = 0$，那么当拆分$b[i]$的时候，又可以让其中一堆等于$b[i]$,另一堆为$0$，这样好像能一直操作下去。

应该是小于，不是不大于。

👍👍

多谢指正

请问一下，总共两堆石子1， 50， 如何分成48， 49？ 拆分的结果不应该依赖于现有的石子数吗？？

拿走1，放入两堆0；
拿走50，放入48和49.

总共两堆加起来才51，哪来的48， 49

注意审题两个新堆的石子总数可以大于取走的那堆石子数

有什么问题吗？？？ 每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子， 这可不会增加石子的总数啊

取走一堆50，放回去48和49有什么问题吗

两个新堆的石子总数可以大于取走的那堆石子数

这肯定有问题啊，哪来的48和49

题目就这么规定，你想拆成多少都可以。。。

石子总数无限，可以随便放，只要新放入的两堆石子，每堆都比取走的一堆小就行

给定 n 堆石子, 何来总数无限这一说

给定 n 堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为 0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。

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

hh

你还是去y总下面评论吧

这里的取走，是直接拿走，放入的时候是从外界放入，与原来的石子数无关的

你理解有误了

请指正，谢谢

所以我说错了吗？

石子的总量是有限的，但实际的情况是多变的。不管玩家如何操作，要确保先手必胜，必须确保能应对所有可能产生的情况----->a[i]划分成(b[i],b[j])为例,不管母堆如何分，只要可能出现的情况都能应对，那么这种情况下我就是必胜的,即单个sg的值等于局部所有可能情况的异或，换句话讲，就是每种可能的sg(i)^sg(j)的集合。然后只需要找出没有出现的最小数S.count(i)返回就可以了

你怎么看这个问题

题目我会做，之前我们讨论的只是，题面表意不清，有人题意没有理解正确，我们给出自己理解的，相对正确的题面，而不是做法。

我以为你说的理解有误，是我题面理解有误，看来不是

然后放入，然后放入仔细体会一下，并不是我从50里面分解，而是我又重新拿了两堆石头，这两堆石头分别总数小于50就行

取走一堆石子，指的是将这堆石子从原本的n堆中移除，“然后放入”，这个放入不是把上一步取走的石子分成两堆放入剩余的 (n - 1) 堆中规模更小的的两堆，而是从外界取得两堆规模更小的石子（即石子数量小于最开始移除的那堆，可以为0），再放入这个石子系统，此时石子总堆数应该是 (n + 1) 堆（可能存在数量为0的堆）,由于没有比0规模更小的石子堆，所以数量为0的堆不能移除

如果是这样，何来拆分一说，这个题的标题是拆分啊，你这样就不叫拆分了啊

如果是这样的话，何来拆分一说，这个题的标题是拆分啊，你这样就不叫拆分了啊

你说的确实有道理，但是这里的拆分也可以理解成原来有n堆石子，拆分成n+1堆石子（拿走一堆石子放入两堆石子），但是拆分不一定要求石子总数是不变的，在拆分过程中，石子堆的数量可能增加（拿走数量为50的，放入48、49），也可能减少（拿走数量为50的堆，放入两堆0）

谢谢这里的每个人，本来我也没读懂题，真的要疯了，看了你们的理解，恍然大悟！

你真是一个鬼才。。你拿走一个放入两个不叫拆分吗？逆天。

每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子。这个题意是不是每次可以从其中一堆石子取，然后再分别放入两堆石子中。取的石子数小于等于原堆石子数即可

不是吧

我明白了，我绕进去了，以为把拿走的那堆，分给其他堆。题目是去掉一堆，再放两个新堆

感谢大佬

我也有你的困惑, 看完评论感觉意思是,: 新放入的两堆石子, 并不局限于 来自之前刚拿走的那堆, 而是有无限多石子可以用来分成两个新堆 加进来?

对，后加进来的两堆石子只要求数量小于原来的那堆即可。

感谢大佬的题解!

如果不是这样，何来拆分一说，这个题的标题是拆分啊，你这样就不叫拆分了啊

为什么拆分的时候枚举 i <= x（i=x的时候）就MLE了呢

每一堆可以变成不大于原来那堆的任意大小的两堆

题目可没有这个限制，题目描述是放入两堆规模更小的石子，可没有说放完后的情况

没有理解你的意思

新放入的两堆总数相加可以大于取出的那一堆，但是新放入的两堆规模都要比取出的那一堆小，这样每堆石子规模都是在减少的，如果枚举$i =x$ 那就不满足新放入的两堆石子规模比取出的一堆石子小，操作不能结束。

你是正解

我想问一下大佬，题目中所说的放回两堆规模更小的石子的意思就是说，放回的两堆的石子个数都小于拿走的那一堆的石子个数吗

是的

谢谢大佬，一开始没搞明白题意

大佬，所以Sinsert的不是把x分为两堆的值，而是把两堆的值加入后的两个新堆的所有可能情况吗？

是的

大佬，我想问下，如果按这题sg里的双重for循环
如果i取x-1,j也取x-1，那么i+j==2x-2,
2x-2有可能会大于x啊，最多不是只能取x个吗

你可能没有看清题意，拆分后的两堆的和可以不等于原来那堆

明白了，谢谢大佬！！！之前纠结了好久

#include <iostream>
#include <cstring>
#include <unordered_set>

using namespace std;

const int N = 110;

int n;
int f[N];
unordered_set<int> S;

int sg(int x)
{
    if(f[x] != -1) return f[x];

    for(int i = 0 ; i < x ; i++)
        for(int j = 0 ; j <= i ; j++)//规定j不大于i，避免重复
            S.insert(sg(i) ^ sg(j));//相当于一个局面拆分成了两个局面，由SG函数理论，多个独立局面的SG值，
                                   //等于这些局面SG值的异或和

    for(int i = 0 ; ; i++)
        if(!S.count(i))
            return f[x] = i;
}

int main()
{
    memset(f , -1 , sizeof f);

    cin >> n;
    int res = 0;
    while(n--)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }

    if(res) puts("Yes");
    else puts("No");
    return 0;
}

为什么你的代码把unordered_set定义在外面也可以AC

没准是数据比较水hh

就离谱

这题中S定义在外面是没关系的，因为每个同一个数字的拆分是递归进行的，这也就说明f[]的求解顺序是从小往大的，例如求sg(100)已经把1到100的值都已经求完了，因为这题拆的情况是只要不等于本身即可，因此一个较小的数的拆分情况完全包括在较大数中，所以S可以开全局

牛子

大佬，我想问一下，2、3最后是怎么分堆的呢？要放入两堆更小的，就是要挑最大的？就把3分成两份，（1，2），（2，1）放入0、2两堆中？分别是（1，4）（2，3） 两种情况？但也没满足 剩下堆的最大值小于被拿的堆啊，，而且 这种结果 不就无限循环了吗？orz

放入的(1,2)是独立的两堆，不会并入剩下的堆中。就拿你说的例子，取走3，还剩下2，再放入(1,2)，剩下的就是1,2,2，因为这些堆的最大值不断减小，所以最后一定会结束。

之所以是1，2，2 而不是 2，3这种情况，是因为要选择对自己最有利的 是吗？

之后放入的那两堆是不会跟剩下的堆合并的，你应该题目理解错了

根据题目意思应该是可以和剩下的堆合并的，只要保证合并后的堆分别严格小于拿的那个堆，之所以两重循环那样写，应该是把所有情况都列举了一遍，因为全部放入新堆规模为0的就是把所有情况都可列举一遍。算法小白 欢迎指正 hh

不可以和剩下的堆合并，放入的两堆更小的石子是独立的堆

那题目“且两个新堆的石子总数可以大于取走的那堆石子数”这个是什么情况下能发生呢 能举个例子嘛

有一堆石子个数为5，拿走这堆，放回两堆大小分别是3和4

a[i] >= b[i] >= b[i]，这里好像写错了

嗯嗯 最后面的应该是b[j]

大佬这速度，赞！

hh 正好看到