2020-2021:teams:legal_string:王智彪:博弈论
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:王智彪:博弈论 [2021/08/15 21:11] 王智彪 |
2020-2021:teams:legal_string:王智彪:博弈论 [2021/09/14 11:20] (当前版本) 王智彪 |
||
|---|---|---|---|
| 行 147: | 行 147: | ||
| 比如 $k=3$ ： | 比如 $k=3$ ： | ||
| - | 由上，只考虑单枚硬币向上的情况。显然 $sg[1]=sg[2]=0,sg[3]=mex(sg[2]^sg[1])=1$ | + | 由上，只考虑单枚硬币向上的情况。显然 $sg[1]=sg[2]=0,sg[3]=mex(sg[2]$ ^ $sg[1])=1$ |
| $N=3t$ 时，先手必赢， $sg[3t]=1$ ，其余必输， $sg[3t+1]=sg[3t+2]=0$ 。 | $N=3t$ 时，先手必赢， $sg[3t]=1$ ，其余必输， $sg[3t+1]=sg[3t+2]=0$ 。 | ||
| - | 因为 $3t$ 翻完之后，会变成 $3t-1$ 和 $3t-2$ 这两种情况的异或和，也就是 $sg[3t]=mex(sg[3t-1]^sg[3t-2])=1$ ，对于 $3t+1$ ，$sg[3t+1]=mex(sg[3t]^sg[3t-1])=mex(1)=0$ ，对于 $3t+2$ ，同理。 | + | 因为 $3t$ 翻完之后，会变成 $3t-1$ 和 $3t-2$ 这两种情况的异或和，也就是 $sg[3t]=mex(sg[3t-1]$ ^ $sg[3t-2])=1$ ，对于 $3t+1$ ，$sg[3t+1]=mex(sg[3t]$ ^ $sg[3t-1])=mex(1)=0$ ，对于 $3t+2$ ，同理。 |
| 推广到别的值也成立。 | 推广到别的值也成立。 | ||
| 行 534: | 行 534: | ||
| 因为如果都配对了，先手做什么后手只需要拿另一堆石子开刀做几乎完全一样的事情就可以继续使石子都配对，这样先手必败，不完全一样的事情是比如 $a,b$ 两堆石子配对数量一样， $a$ 拿走之后又取了一堆之后消失了，这样 $b$ 还给 $a$ 的那部分可以归到取走里，这样还是配对的。 | 因为如果都配对了，先手做什么后手只需要拿另一堆石子开刀做几乎完全一样的事情就可以继续使石子都配对，这样先手必败，不完全一样的事情是比如 $a,b$ 两堆石子配对数量一样， $a$ 拿走之后又取了一堆之后消失了，这样 $b$ 还给 $a$ 的那部分可以归到取走里，这样还是配对的。 | ||
| - | 如果不完全配对，我们选择出现奇数次中最大的石子堆，比如现在是 $2 6 8 9$ ，然后拿 $9$ 这一堆，至少拿一个变成 $8$ ，然后我们把 $6$ 这堆补到 $8$ ，然后 $8$ 变成 $6$ ，再接着找更少的，如果最开始奇数的堆数是偶数，就把自己保留到最少的那堆石子数，不然剩下的也取走，这样保证所有都配对，后手必败，所以先手必胜。 | + | 如果不完全配对，我们选择出现奇数次中最大的石子堆，比如现在是 $2\ 6\ 8\ 9$ ，然后拿 $9$ 这一堆，至少拿一个变成 $8$ ，然后我们把 $6$ 这堆补到 $8$ ，然后 $8$ 变成 $6$ ，再接着找更少的，如果最开始奇数的堆数是偶数，就把自己保留到最少的那堆石子数，不然剩下的也取走，这样保证所有都配对，后手必败，所以先手必胜。 |
| <hidden 代码> | <hidden 代码> | ||
2020-2021/teams/legal_string/王智彪/博弈论.1629033093.txt.gz · 最后更改: 2021/08/15 21:11 由 王智彪
