每次加装滤镜,相当于把灯带上全体亮度编码同时异或某个当前仍存在的编码。关键观察:若干次操作后,整体等价于把所有元素都异或了某个 g,且 g 只能是 0 或原数组中的某个 ai。
因此只需在候选集合 G={0}∪{ai} 中最大化
S(g)=i=1∑n(ai⊕g).美术馆正在调试一条由 n 盏灯组成的展陈灯带,第 i 盏灯的亮度编码为非负整数 ai。控制室允许任意次(也可以零次)加装同一款滤镜:每次必须从当前灯带上选出某一盏灯的编码 x,然后把每一盏灯的编码同时变成 ai⊕x(按位异或)。滤镜可以叠加,但每一次所用的 x 都必须取自操作当时灯带上仍然存在的某个编码。
策展方希望灯带的亮度编码之和尽可能大,以便在能耗报表里拿到更高的展示评分。请计算操作结束后数组元素之和的最大值。
约束:测试组数不超过 200000,单组灯数不超过 200000,单个测试文件中所有 n 之和不超过 200000,每个 ai 不超过 1000000000。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册