2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2 [2020/06/25 22:00] jjleo [F] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2 [2020/06/25 22:10] (当前版本) jjleo [F] |
||
|---|---|---|---|
| 行 29: | 行 29: | ||
| =====F===== | =====F===== | ||
| - | * 题意:博（巴）弈（耶）论（力）。一共有$t$轮游戏，每次有两个数字$s$和$e$，两人轮流操作，可以将$s$变为$s+1$或$2s$，先将$s$变为大于$e$的数的人输。每一轮输的人下一轮先手，最终是否胜利取绝于最后一轮。第一轮你先手，问你是否有：无论对手如何操作都必胜的方案，和无论对手如何操作都必输的方案。 | + | * 题意:博（巴）弈（耶）论（力）。一共有$t$轮游戏，每次有两个数字$s$和$e(s \le e)$，两人轮流操作，可以将$s$变为$s+1$或$2s$，先将$s$变为大于$e$的数的人输。每一轮输的人下一轮先手，最终是否胜利取绝于最后一轮。第一轮你先手，问你是否有：无论对手如何操作都必胜的方案，和无论对手如何操作都必输的方案。 |
| * 题解:本质就是判断每一轮双方都在最优/差策略下，是先手必胜还是后手必胜，是先手必输还是后手必输，这样我们就可以判断每一轮是否可以必先手和是否可以必后手，进一步判断下一轮的状态，直到最后一轮。设$win(s,e)$为初始条件为$s,e$时先手是否必胜。 | * 题解:本质就是判断每一轮双方都在最优/差策略下，是先手必胜还是后手必胜，是先手必输还是后手必输，这样我们就可以判断每一轮是否可以必先手和是否可以必后手，进一步判断下一轮的状态，直到最后一轮。设$win(s,e)$为初始条件为$s,e$时先手是否必胜。 | ||
| - | * 对于一轮游戏，如果$e$是奇数，那么如果$$ | + | * 如果$e$是奇数，如果$s$是偶数，每次只需要$+1$，对手无论哪种操作都会将$s$变为偶数，若超过$e$你直接获胜，否则你继续$+1$得到的值依旧是奇数不会超过$e$，因此先手必胜。反过来$s$是奇数则后手必胜。 |
| + | * 如果$e$是偶数，$2s>e$，双方都不能用翻倍，因此只能一个个加，那么$s$是奇数必胜，否则后手必胜。 | ||
| + | * 如果$e$是偶数，$4s>e$，那么先手可以控制到达$2s>e$时$s$的奇偶性，因此先手必胜。 | ||
| + | * 如果$e$是偶数，$4s \le e$，那么答案等同于$win(s,\frac{e}{4})$，因为如果先手可以让对方先超过$\frac{e}{4}$，相当于让自己到达了$4s>e$的状态，因此先手必胜，否则后手必胜。 | ||
| + | |||
| + | |||
| + | * 考虑先手是否必输，如果$2s>e$，显然直接乘就输了，因此先手必输。 | ||
| + | * 否则答案和$win(s,\frac{e}{2})$相同，因为如果先手可以让对方先超过$\frac{e}{2}$，相当于让自己到达了$2s>e$的状态，因此先手必输，否则后手必输。 | ||
2020-2021/teams/farmer_john/jjleo/codeforces_round_652_div._2.1593093611.txt.gz · 最后更改: 2020/06/25 22:00 由 jjleo
