Codeforces Round 1937 解题报告

A Shuffle Party

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

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

B Binary Path

开始和结尾是固定的。

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

C Bitwise Operation Wizard

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

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

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

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

D Pinball

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

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

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

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

前缀和优化即可。

E Pokémon Arena

建图题。

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

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

发表回复

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

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据