2020-2021:teams:manespace:cf_659_div.2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:manespace:cf_659_div.2 [2020/07/31 13:11]
quantumbolt 创建
+++ 2020-2021:teams:manespace:cf_659_div.2 [2020/07/31 13:53] (当前版本)
quantumbolt
@@ 行 43: / 行 43: @@
 Koa和KoalaKoala两人玩游戏，初始分均为$0$，每次两人从一个数组中选择一个数，选择后该数字会被从数组中删除，两人的分数异或上该数字的值为新的分数，问均采取最优策略谁能赢，规定KoaKoa先手。
 ===== 题解 =====
+这个题是博弈论的题：
+分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数
+若$2|p_i$那么先手和后手对$i$位的结果没有影响
+从而我们需要找到$j$，使得$2|p_j=1$这样才能导致先后手的结果在第$j$位不同
+现在我们的任务就是找打最大的$j$位，使结果最大化
+. 若$\frac{P_j-1}{2}$是偶数，那么先手的就一定赢
+先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。
+. 若$\frac{P_j-1}{2}$是奇数，分两种情况
+(1). 若$2|n = 1$先手就必输：
+先手在该位先取一个1，然后跟着后手选，那么后手会择偶数个1，结果为：先手在该位值为1，后手为0。
+(2). 若$2|n$那么先手必赢
+先手第一步选一个0，然后将状态转为$2|n=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。
-这个题是博弈论的题： 分析一下： 设$p_i$表示$n$个数二进制位第$i$位为$1$的个数 若$p_i|2$那么先手和后手对$i$位的结果没有影响 从而我们需要找到$j$，使得$p_j|2=1$这样才能导致先后手的结果在第$j$位不同 现在我们的任务就是找打最大的$j$位，使结果最大化 若$\frac{P_j-1}{2}$是偶数，那么先手的就一定赢 - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 若$\frac{P_j-1}{2}$是奇数，分两种情况 1. 若$n|1 = 1$先手就必输： - 先手在该位先取一个1，然后跟着后手选，那么后手会选择偶数个1，结果为：先手在该位值为1，后手为0。 2. 若$n|1$那么先手必赢 - 先手第一步选一个0，然后将状态转为$n|2=1$的局面，且轮到后手先选择，上面已经证明，这种局面先选择的必输。
 ====== E String Transformation 2 ======

2020-2021/teams/manespace/cf_659_div.2.1596172305.txt.gz · 最后更改: 2020/07/31 13:11 由 quantumbolt