2020-2021:teams:manespace:cf_659_div.2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:manespace:cf_659_div.2 [2020/07/31 13:35] quantumbolt |
2020-2021:teams:manespace:cf_659_div.2 [2020/07/31 13:53] (当前版本) quantumbolt |
||
|---|---|---|---|
| 行 45: | 行 45: | ||
| 这个题是博弈论的题： | 这个题是博弈论的题： | ||
| 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 | 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 | ||
| - | 若$p_i|2$那么先手和后手对$i$位的结果没有影响 | + | 若$2|p_i$那么先手和后手对$i$位的结果没有影响 |
| - | 从而我们需要找到$j$，使得$p_j|2=1$这样才能导致先后手的结果在第$j$位不同 | + | 从而我们需要找到$j$，使得$2|p_j=1$这样才能导致先后手的结果在第$j$位不同 |
| 现在我们的任务就是找打最大的$j$位，使结果最大化 | 现在我们的任务就是找打最大的$j$位，使结果最大化 | ||
| 行 54: | 行 54: | ||
| 2. 若$\frac{P_j-1}{2}$是奇数，分两种情况 | 2. 若$\frac{P_j-1}{2}$是奇数，分两种情况 | ||
| - | (1). 若$n|1 = 1$先手就必输： | + | (1). 若$2|n = 1$先手就必输： |
| 先手在该位先取一个1，然后跟着后手选，那么后手会择偶数个1，结果为：先手在该位值为1，后手为0。 | 先手在该位先取一个1，然后跟着后手选，那么后手会择偶数个1，结果为：先手在该位值为1，后手为0。 | ||
| - | (2). 若$n|1$那么先手必赢 | + | (2). 若$2|n$那么先手必赢 |
| - | 先手第一步选一个0，然后将状态转为$n|2=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。 | + | 先手第一步选一个0，然后将状态转为$2|n=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。 |
| ====== E String Transformation 2 ====== | ====== E String Transformation 2 ====== | ||
2020-2021/teams/manespace/cf_659_div.2.1596173756.txt.gz · 最后更改: 2020/07/31 13:35 由 quantumbolt
