给定一个数组,我必须找到其大小大于或等于2的给定数组的所有可能子集的最大和最小元素的所有位或最大值的总和。
例-[1,3,5]
大小大于等于2的子集是{1,3}{1,5}{3,5}{1,3,5}
{1,3}-此子集中max和min元素的双向或=3
{1,5}-此子集中max和min元素的双向或=5
{3,5}-此子集中max和min元素的双向或=7
{1,3,5}-此子集中max和min元素的双向或=5
所以总和是3+5+7+5=20。
我试图用给定集合的位和或所有可能子集的和进行修改,但无法绘制逻辑。
注意:数组的大小是10^5。

最佳答案

对数组排序。循环查看集合中的所有元素对任何将这些元素作为min和max的子集都将提供相同的贡献由于数组是排序的,因此可以通过元素的索引计算此类子集的数量。然后,您可以将这些子集的组合贡献计算为子集的按位或乘以数。

10-06 05:24
查看更多