Codeforces Round 1937 解题报告

A Shuffle Party

容易观察到在 2x2 \cdot x 的时候一就会被交换出去。

输出最小的 2 的次幂即可。

B Binary Path

开始和结尾是固定的。

扫描两层中间的部分,只能走上面就归 0,都能走 +1, 只能走下面就结束。

C Bitwise Operation Wizard

先 n 次打擂台,找到最大值。

很容易发现 aiaja_i \oplus a_j 的最大值应该是 2k12^k-1

所以我们可以可以再打一次擂台,找到 amaia_m | a_i 的最大值及其合法 aia_i 序列(其中 ama_m 是已经找到的最大值)。

然后现在要想异或是也能这么优,我们需要找到最小的 aia_i,再打一次擂台即可。

D Pinball

什么史诗级分类讨论大题。

容易发现球在滚来滚去,最后出去。

球会因为在其左边的 > 和在其右边的 < 的反弹一次。

故事实上求会反弹有限次,且反弹的点位是确定的。

前缀和优化即可。

E Pokémon Arena

建图题。

考虑直接建图描述这个情况,很容易发现复杂度是 O(n2m)O(n^2m) 的,绷不住。

考虑将每个属性的当前值抽出来建图,这样建图复杂度就是 O(nm)O(nm) 的,就可以正常通过此题。

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

message
account_circle
Please input name.
email
Please input email address.
links

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理