g*s
2 楼
题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
１比较容易，２难一些.
可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
１比较容易，２难一些.
m*e
3 楼
大家I140递上去后网上看到的是acceptance,还是initial review?我们的case non-pp，为啥看到是initial review?太奇怪了。
谢谢
谢谢
s*s
4 楼
rt, 发包子求perm 广告模板。硕士工科。
g*e
5 楼
第一题先取的人必胜，只要每次都把一堆留下两根，剩下的都拿走。不管第二个人怎么
拿，都有必胜的办法。
第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
拿，都有必胜的办法。
第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
V*a
6 楼
我从efile后之后，就一直都是initial review
pp，为啥看到是initial review?太奇怪了。
【在 m********e 的大作中提到】
: 大家I140递上去后网上看到的是acceptance,还是initial review?我们的case non-pp，为啥看到是initial review?太奇怪了。
: 谢谢
pp，为啥看到是initial review?太奇怪了。
【在 m********e 的大作中提到】
: 大家I140递上去后网上看到的是acceptance,还是initial review?我们的case non-pp，为啥看到是initial review?太奇怪了。
: 谢谢
b*w
7 楼
恭喜，baozi
g*s
8 楼
只能从"一堆"中取
【在 g**e 的大作中提到】
: 第一题先取的人必胜，只要每次都把一堆留下两根，剩下的都拿走。不管第二个人怎么
: 拿，都有必胜的办法。
: 第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
:
: ，可
【在 g**e 的大作中提到】
: 第一题先取的人必胜，只要每次都把一堆留下两根，剩下的都拿走。不管第二个人怎么
: 拿，都有必胜的办法。
: 第二题还没想特别清楚，感觉如果是奇数堆火柴，先拿取胜。偶数堆就是后拿取胜
:
: ，可
m*e
9 楼
奥，那就是正常。我放心了。
iY
10 楼
congratulations, 吃
g*e
11 楼
不是有若干堆吗，你的意思是一堆没取完，不能动下一堆？
【在 g***s 的大作中提到】
: 只能从"一堆"中取
【在 g***s 的大作中提到】
: 只能从"一堆"中取
s*s
12 楼
多谢，可是要给模板才有包子呀. at least could you please give some idea of
the essential components for such an advertisement? thx
the essential components for such an advertisement? thx
g*s
13 楼
一次从两堆里取
【在 g**e 的大作中提到】
: 不是有若干堆吗，你的意思是一堆没取完，不能动下一堆？
【在 g**e 的大作中提到】
: 不是有若干堆吗，你的意思是一堆没取完，不能动下一堆？
s*c
14 楼
模版现在没有，不过给你个建议，千万别留email，收简历地址用邮寄的，这样基本就
没人投简历了。
没人投简历了。
A*M
15 楼
1是比较简单。异或所有堆的数目。每次从某堆取一些， 使这个异或值为0。
2也类似吧。 还在想。
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
2也类似吧。 还在想。
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
s*s
16 楼
好的
p*3
18 楼
Sent to you.
b*r
19 楼
nim number problem. (1) make all nums xor equals to 0 (2) make all nums xor
equals to 1
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
equals to 1
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
s*s
20 楼
谢谢，请收包子。
【在 s********c 的大作中提到】
: 模版现在没有，不过给你个建议，千万别留email，收简历地址用邮寄的，这样基本就
: 没人投简历了。
【在 s********c 的大作中提到】
: 模版现在没有，不过给你个建议，千万别留email，收简历地址用邮寄的，这样基本就
: 没人投简历了。
g*e
21 楼
各位大牛都太厉害了
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
s*s
22 楼
谢谢，双黄包奉上。
【在 p*****3 的大作中提到】
: Sent to you.
【在 p*****3 的大作中提到】
: Sent to you.
g*y
23 楼
我是后知后觉 + 偷懒 + 问人 + Google，Bravethinker是博学
【在 g**e 的大作中提到】
: 各位大牛都太厉害了
【在 g**e 的大作中提到】
: 各位大牛都太厉害了
r*y
24 楼
consider the simple case firstly ?
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
g*s
25 楼
2不对。
比如 3 3 3 3
xor
【在 b**********r 的大作中提到】
: nim number problem. (1) make all nums xor equals to 0 (2) make all nums xor
: equals to 1
:
: ，可
比如 3 3 3 3
xor
【在 b**********r 的大作中提到】
: nim number problem. (1) make all nums xor equals to 0 (2) make all nums xor
: equals to 1
:
: ，可
g*s
26 楼
这个只给了1的解答。1是比较容易的。
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
g*y
27 楼
3 3 3 3想起来比较抽象，{3，2}就可以。
按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
【在 g***s 的大作中提到】
: 2不对。
: 比如 3 3 3 3
:
: xor
按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
【在 g***s 的大作中提到】
: 2不对。
: 比如 3 3 3 3
:
: xor
g*s
28 楼
我是说3 3 3 3 按这个方法不对。
3 3 3 3实际是必败的一个状态.
【在 g**********y 的大作中提到】
: 3 3 3 3想起来比较抽象，{3，2}就可以。
: 按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
3 3 3 3实际是必败的一个状态.
【在 g**********y 的大作中提到】
: 3 3 3 3想起来比较抽象，{3，2}就可以。
: 按XOR=1, player 1该取成{1, 2}, 但是player 2把2取走，player 1就必胜了。
g*e
29 楼
偶数堆先拿必败吧，我感觉
【在 g***s 的大作中提到】
: 我是说3 3 3 3 按这个方法不对。
: 3 3 3 3实际是必败的一个状态.
【在 g***s 的大作中提到】
: 我是说3 3 3 3 按这个方法不对。
: 3 3 3 3实际是必败的一个状态.
g*s
30 楼
不一定。例如3 1 1 1 或者1 1
【在 g**e 的大作中提到】
: 偶数堆先拿必败吧，我感觉
【在 g**e 的大作中提到】
: 偶数堆先拿必败吧，我感觉
g*e
31 楼
1 1 怎么不是先拿必败？第一个人只能拿一根，第二个人就赢了
是不是我理解错了第二题意？
【在 g***s 的大作中提到】
: 不一定。例如3 1 1 1 或者1 1
是不是我理解错了第二题意？
【在 g***s 的大作中提到】
: 不一定。例如3 1 1 1 或者1 1
g*s
32 楼
取到最后一根的败啊
【在 g**e 的大作中提到】
: 1 1 怎么不是先拿必败？第一个人只能拿一根，第二个人就赢了
: 是不是我理解错了第二题意？
【在 g**e 的大作中提到】
: 1 1 怎么不是先拿必败？第一个人只能拿一根，第二个人就赢了
: 是不是我理解错了第二题意？
g*s
33 楼
这是大学算法课的一个作业。后来发到了学校的bbs上，刚刚查了一下，居然有人放到
blog里面了。
http://blog.163.com/[email protected]/blog/static/13702062420100
先解决第1题
定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
态，用S表示。
定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
,则存在A(t), A(t) xor c 证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，c的第p位就也为0，矛盾
！）
x=a(t) xor c 的第p位将为1 xor 1,即0；
又因为c的最高位为p，所以x高于p位的值不变。所以必有x. 命题得证。
再来证定理1.
证明：
设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
记c=A(1) xor A(2) xor …… xor A(n),
因为是S态，所以 c>0;
所以存在A(t), A(t) xor c A(t)' = A(t) xor c c' = A(1) xor A(2) xor … xor A(t)' xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor … xor A(n) xor c
= c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c 故命题成立。 #
定理2：T态，取任何一堆的若干根，都将成为S态。
证明：反证法：
反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
A(m)>A(m)' 状态均为T态。
记c=A(1) xor A(2) xor … xor A(m) xor… xor A(n),
记c'=A(1) xor A(2) xor … xor A(m)' xor… xor A(n),
c=0;c'=0;
所以有 0= A(1) xor A(2) xor … xor A(m) xor… xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
同理， d xor A(m)' =0
A(m)'= d
所以，A(m)'=A(m) . 矛盾！
故反设不成立。原命题成立。 #
定理 3：S态，只要方法正确，必赢。
最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，可以把它
变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己
方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #
定理4：T态，只要对方法正确，必败。
由定理3易得。
我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着主动权
。经过分析，我们有以下结论：
定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的
堆数等于0，则称为部分利他态，用T0表示。
定理4：不存在充裕堆数为1的T态。
证明：
孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。
一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充裕堆的
堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利己态
，用S0表示。
定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对方取
，所以最后一根必己取。败。
同理, T0态必胜#
定理5：S1态，只要方法正确，必胜。
证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
这样，就变成奇数个孤单堆，由对方取。
由定理4，对方必输。己必胜。 #
定理6：S2态不可转一次变为T0态。
证明：充裕堆数不可能一次由2变为0。得证。 #
定理7：S2态可一次转变为T2态。
证明：由定理1，S态可转变为T态，态可一次转变为T态
又由定理6，S2态不可转一次变为T0态，
所以转变的T态为T2态。 #
定理8：T2态，只能转变为S2态或S1态。
证明：. 由定理2，T态必然变为S态。
由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
命题得证。
定理9：S2态，只要方法正确，必胜.
证明：方法如下：
1） S2态，就把它变为T2态。（由定理7）
2） 对方只能T2转变成S2态或S1态(定理8)
若转变为S2, 转向1）
若转变为S1, 这己必胜。（定理5）
定理10：T2态必输。
证明：同9。
综上所述，必输态有： T2,S0
必胜态： S2,S1,T0.
两题比较：
第一题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为T0（
第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为T0）
,也可以使对方得到最后一根（转变为S0）。
所以，抢夺S1是制胜的关键！
为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.(见定
理9的证明).
blog里面了。
http://blog.163.com/[email protected]/blog/static/13702062420100
先解决第1题
定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
态，用S表示。
定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
,则存在A(t), A(t) xor c 证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
二进制的第p位也是1。（否则，若所有的A(i)的第p位都是0，c的第p位就也为0，矛盾
！）
x=a(t) xor c 的第p位将为1 xor 1,即0；
又因为c的最高位为p，所以x高于p位的值不变。所以必有x. 命题得证。
再来证定理1.
证明：
设共有n堆火柴，每堆的数目分别为A(i)，i=1..n，A(i)为非副整数.
记c=A(1) xor A(2) xor …… xor A(n),
因为是S态，所以 c>0;
所以存在A(t), A(t) xor c A(t)' = A(t) xor c c' = A(1) xor A(2) xor … xor A(t)' xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor c xor … xor A(n)
= A(1) xor A(2) xor … xor A(t) xor … xor A(n) xor c
= c xor c = 0
所以，用把第t堆由A(t)根取成A(t)' 根（A(t)' = A(t) xor c 故命题成立。 #
定理2：T态，取任何一堆的若干根，都将成为S态。
证明：反证法：
反设存在一堆，记为第m堆，从中取了若干根，根数由A(m)变为A(m)' .
A(m)>A(m)' 状态均为T态。
记c=A(1) xor A(2) xor … xor A(m) xor… xor A(n),
记c'=A(1) xor A(2) xor … xor A(m)' xor… xor A(n),
c=0;c'=0;
所以有 0= A(1) xor A(2) xor … xor A(m) xor… xor A(n)
= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n) xor A(m)
= d xor A(m)
d= A(1) xor A(2) xor … xor A(m-1) xor A(m+1) xor… xor A(n)
故 A(m)=d
同理， d xor A(m)' =0
A(m)'= d
所以，A(m)'=A(m) . 矛盾！
故反设不成立。原命题成立。 #
定理 3：S态，只要方法正确，必赢。
最终胜利即由S态转变为T态，任何一个S态，只要把它变为T态，（由定理一，可以把它
变成T态。）对方只能把T态转变为S态(定理2)。这样，所有S态向T态的转变都可以有己
方控制，对方只能被动地实现由T态转变为S态。故S态必赢。 #
定理4：T态，只要对方法正确，必败。
由定理3易得。
我们再来处理第2题。我们会发现两题会有一些相同之处，控制S->T态的人控制着主动权
。经过分析，我们有以下结论：
定义2：若一堆中仅有1根火柴，则被称为孤单堆。若大于1根，则称为充裕堆。
定义3：T态中，若充裕堆的堆数大于等于2，则称为完全利他态，用T2表示；若充裕堆的
堆数等于0，则称为部分利他态，用T0表示。
定理4：不存在充裕堆数为1的T态。
证明：
孤单堆的根数异或只会影响二进制的最后一位，但充裕堆会影响高位（非最后一位）。
一个充裕堆，高位必有一位不为0，则所有根数异或不为0。故不会是T态。
定义4：S态中，若充裕堆的堆数大于等于2，则称为完全利己态，用S2表示；若充裕堆的
堆数等于1，则称为自主利己态，用S1表示; 若充裕堆的堆数等于0，则称为部分利己态
，用S0表示。
定理4：S0态，即仅有奇数个孤单堆，必败。T0态必胜。
证明：S0态，其实就是每次只能取一根。每次第奇数根都由己取，第偶数根都由对方取
，所以最后一根必己取。败。
同理, T0态必胜#
定理5：S1态，只要方法正确，必胜。
证明：若此时孤单堆堆数为奇数，把充裕堆取完；否则，取成一根。
这样，就变成奇数个孤单堆，由对方取。
由定理4，对方必输。己必胜。 #
定理6：S2态不可转一次变为T0态。
证明：充裕堆数不可能一次由2变为0。得证。 #
定理7：S2态可一次转变为T2态。
证明：由定理1，S态可转变为T态，态可一次转变为T态
又由定理6，S2态不可转一次变为T0态，
所以转变的T态为T2态。 #
定理8：T2态，只能转变为S2态或S1态。
证明：. 由定理2，T态必然变为S态。
由于充裕堆数不可能一次由2变为0，所以此时的S态不可能为S0态。
命题得证。
定理9：S2态，只要方法正确，必胜.
证明：方法如下：
1） S2态，就把它变为T2态。（由定理7）
2） 对方只能T2转变成S2态或S1态(定理8)
若转变为S2, 转向1）
若转变为S1, 这己必胜。（定理5）
定理10：T2态必输。
证明：同9。
综上所述，必输态有： T2,S0
必胜态： S2,S1,T0.
两题比较：
第一题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->T0->S0->T0->……->S0->T0(全0)
第二题的全过程其实如下：
S2->T2->S2->T2-> …… ->T2->S1->S0->T0->S0->……->S0->T0(全0)
下划线表示胜利一方的取法。
是否发现了他们的惊人相似之处。
我们不难发现(见加黑部分)，S1态可以转变为S0态（第二题做法），也可以转变为T0（
第一题做法）。哪一方控制了S1态，他即可以有办法使自己得到最后一根（转变为T0）
,也可以使对方得到最后一根（转变为S0）。
所以，抢夺S1是制胜的关键！
为此，始终把T2态让给对方，将使对方处于被动状态，他早晚将把状态变为S1.(见定
理9的证明).
g*y
34 楼
如果没有见过解法，面试时就解出来，也太牛了。我是慢慢想都只能解特殊情况。不知道什么时候能全解。
>0
【在 g***s 的大作中提到】
: 这是大学算法课的一个作业。后来发到了学校的bbs上，刚刚查了一下，居然有人放到
: blog里面了。
: http://blog.163.com/[email protected]/blog/static/13702062420100
: 先解决第1题
: 定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
: 态，用S表示。
: 定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
: 引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
: ,则存在A(t), A(t) xor c : 证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
>0
【在 g***s 的大作中提到】
: 这是大学算法课的一个作业。后来发到了学校的bbs上，刚刚查了一下，居然有人放到
: blog里面了。
: http://blog.163.com/[email protected]/blog/static/13702062420100
: 先解决第1题
: 定义1：若所有火柴数异或为0，则该状态被称为利他态，用字母T表示；否则，为利己
: 态，用S表示。
: 定理1：对任何S态，存在方法，从其中取一堆中的若干根，使状态变为T态。
: 引理1.1 ：A(i)为非副整数，i=1..n, 记c=A(1) xor A(2) xor …… xor A(n),若c>0
: ,则存在A(t), A(t) xor c : 证明： 把c表示成二进制，记它的二进制数的最高位为第p位，则必然存在一个A(t),它
g*s
35 楼
这个做面试题太难。是一道课后选题，老师也没有答案的那种。
知道什么时候能全解。
【在 g**********y 的大作中提到】
: 如果没有见过解法，面试时就解出来，也太牛了。我是慢慢想都只能解特殊情况。不知道什么时候能全解。
:
: >0
知道什么时候能全解。
【在 g**********y 的大作中提到】
: 如果没有见过解法，面试时就解出来，也太牛了。我是慢慢想都只能解特殊情况。不知道什么时候能全解。
:
: >0
d*l
36 楼
稍微难了点，自己真想不出来。。
s*y
37 楼
这个真是google得面试题阿
http://23.latest.careercup.appspot.com/question?id=174666
【在 g***s 的大作中提到】
: 这个做面试题太难。是一道课后选题，老师也没有答案的那种。
:
: 知道什么时候能全解。
http://23.latest.careercup.appspot.com/question?id=174666
【在 g***s 的大作中提到】
: 这个做面试题太难。是一道课后选题，老师也没有答案的那种。
:
: 知道什么时候能全解。
F*r
38 楼
game theory, simple DP, only 2 values for each state case, win or lose
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
g*s
39 楼
第一题做面试没问题，并不难。第二题做面试要现场做出来难。
【在 s*****y 的大作中提到】
: 这个真是google得面试题阿
: http://23.latest.careercup.appspot.com/question?id=174666
【在 s*****y 的大作中提到】
: 这个真是google得面试题阿
: http://23.latest.careercup.appspot.com/question?id=174666
d*e
40 楼
看来现在的面试,数学差点都不行...
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
【在 g**********y 的大作中提到】
: http://en.wikipedia.org/wiki/Nim
b*y
41 楼
好像第二问就是留一根给对方就行了
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
，可
【在 g***s 的大作中提到】
: 题目1： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，
: 可将一堆全取走，但不可不取，最后取完者为胜，求必胜的方法。
: 题目2： 今有若干堆火柴，两人依次从中拿取，规定每次只能从一堆中取若干根，可
: 将一堆全取走，但不可不取，最后取完者为负，求必胜的方法。
: １比较容易，２难一些.
N*2
42 楼
拜托
人家明明给了1和2的答案
仔细看
【在 g***s 的大作中提到】
: 这个只给了1的解答。1是比较容易的。
人家明明给了1和2的答案
仔细看
【在 g***s 的大作中提到】
: 这个只给了1的解答。1是比较容易的。
g*s
43 楼
哦。不好意思，没看仔细。
呵呵。
【在 N*2 的大作中提到】
: 拜托
: 人家明明给了1和2的答案
: 仔细看
呵呵。
【在 N*2 的大作中提到】
: 拜托
: 人家明明给了1和2的答案
: 仔细看
g*y
44 楼
赞知错就改！
【在 g***s 的大作中提到】
: 哦。不好意思，没看仔细。
: 呵呵。
【在 g***s 的大作中提到】
: 哦。不好意思，没看仔细。
: 呵呵。
相关阅读
第一次收到AP，两份一模一样的纸，对吗？请问EB3 可以升级到EB2吗各地议员打个分吧-尤其是通过议员帮助绿了的版友【EB2 2016年四月第1绿】NSC 主副同绿 PD：08/08/2012OPT递交485 的问题【EB2 2016年四月第3绿】原装EB2 TSC 2/2012主副同时approvedTSC原装EB3 pd 12/2012， rd 10/2015催绿感受"Document Was Mailed To Me" What does this mean???用失效的EAD工作有什么后果NIU能不能问一下奥本对今年FB绿卡overflow到EB的展望？关于ead renew的问题求问：我这种情况应该怎样递交H4 EAD申请？谢谢！降级or新增一个140?【EB3 2016年3月第52绿】PD：5/15/2013 EB2 ->EB3ead renew问题EB2 -> EB3 PP approved 现在要做什么问个EAD延期的弱智问题，望轻拍【EB2 2016年三月第87绿】原装 NSC PD 5/2012EB2， PD 3/2012 RD 5/2015， 今天SR的结果