【题解】2021牛客OI赛前集训营-提高组(第七场)
UPD: std 链接
A https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033117
B https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033126
C https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033140
D https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49033129
依依寺
我们考虑先后手的策略, 的作用仅仅是改变后续操作的奇偶性,因此 的个数 可以对 取模。
接下来,我们先不考虑 的存在。
先手取了 之后,后手必定取 ,然后先后手依次是 ;
先手取了 之后,后手必定取 ,然后先后手依次是 。
综上,观察到取的方式一定是 交替(除了开头)。
有额外一个 即可以调控上述的某次操作的先后手关系,分类讨论即可。
当然,此类博弈题一个比较合适的方式是打表找规律。
时间复杂度 。
武义寺
设该数列最早在 位置出现 ,令 ,枚举 ,则前 个数的可行的方案为
因此答案为:
时间复杂度: 。
依久依久
首先,求 可以转化为求前缀异或和 ,那么答案就是 。
我们考虑递归的求 ,即找到最大的一个 满足 ,那么
找到这个 可以在预处理的 数列上二分。
注意到斐波那契数列和 的幂次类似,递归执行只会访问到 种 ,故记忆化搜索即可。
时间复杂度 。
补幺梨
对于 较小的情况,猜测最大不能被表示的数不太大,那么就可以直接跑完全背包,用 bitset 优化。
不妨假设 ,对于模 跑同余最短路, 表示最小的模 的数,则 均可被表示出来(不停加入 ),因此答案就是 。
考虑到 序列纯随机, 个在 中等概率随机的整数的最小值是 的。
因此我们取最小的这个数作为 跑 spfa 即可,时间复杂度 。