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 15:54] jjleo [E] |
2020-2021:teams:farmer_john:jjleo:codeforces_round_652_div._2 [2020/06/25 22:10] (当前版本) jjleo [F] |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| =====D===== | =====D===== | ||
| - | * 题意:鬼畜的树。 | + | * 题意:鬼畜的树。每次每个点都会进行如下生长：如果是叶子节点，就增加一个子节点；如果有一个子节点，就增加两个子节点；否则不生长。问第$n$次生长后可以选择多少个不重叠的爪子，即一个父节点和三个子节点。 |
| - | * 题解: | + | * 题解:画图可以发现如果只考虑新长的树，两次前的节点全都会长成爪子，因此有$f_i=f_{i-1}+2f_{i-2}$。这只是考虑了所有最新长的，画图可以发现每过$3$个就可以把之前的也选上，因此答案最后要加上$f(n-3),f(n-6)...$。也可以考虑每过$3$个就可以选上一个新根，即$f_i=f_{i-1}+2f_{i-2}+[i \mod 3 = 0]$ |
| =====E===== | =====E===== | ||
| 行 29: | 行 29: | ||
| =====F===== | =====F===== | ||
| - | * 题意: | + | * 题意:博（巴）弈（耶）论（力）。一共有$t$轮游戏，每次有两个数字$s$和$e(s \le e)$，两人轮流操作，可以将$s$变为$s+1$或$2s$，先将$s$变为大于$e$的数的人输。每一轮输的人下一轮先手，最终是否胜利取绝于最后一轮。第一轮你先手，问你是否有：无论对手如何操作都必胜的方案，和无论对手如何操作都必输的方案。 |
| - | * 题解: | + | * 题解:本质就是判断每一轮双方都在最优/差策略下，是先手必胜还是后手必胜，是先手必输还是后手必输，这样我们就可以判断每一轮是否可以必先手和是否可以必后手，进一步判断下一轮的状态，直到最后一轮。设$win(s,e)$为初始条件为$s,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.1593071677.txt.gz · 最后更改: 2020/06/25 15:54 由 jjleo
