解题思路
使用第 i 个模块时,可以或上任意满足 0≤x≤ai 的整数。最终结果等于若干个这样的 x 的按位或,目标是让这个值尽量大。
先统计每一位上有多少个 ai 该位为 1。从高位到低位考虑:
- 若第 i 位至少出现一次,则最终答案必须带上这一位:因为 2i>2i−1+⋯+20,放弃它不可能用更低位补回来。消耗一次该位的计数。
- 若消耗后该位仍有剩余(至少还有一个上限带着这一位),则这个上限至少为 2i,因此可以选出不超过它、且把第 0 到 i−1 位全部置
1 的数。此时答案可以填满所有更低位,直接结束。