题解：CF2146D1 Max Sum OR (Easy Version)

沉石鱼惊旋 · 2025-09-25 14:50:03 · 题解

这里是一个仅能做 D1 的解法。

我们通过手摸若干个数据，可以发现，我们存在如下的一个贪心构造：先得到一个最大的 p=(11\dots1)_2，满足 p\geq r。之后，从 r 开始，倒着往 0 匹配。如果存在 p-i 这个数，就 a_{i}=p-i。否则，我们 p\gets p/2，然后重复这个过程。

理解一下这个为什么是对的？我们其实就是每次取出了一段后缀，拼出了一个极大的答案。这个类似于递归的过程，我先处理一部分，然后递归到子问题。

cpp 提交记录：https://codeforces.com/contest/2146/submission/339811056

py 提交记录：https://codeforces.com/contest/2146/submission/339811079