此题思路,建议思考无果后观看,大神勿喷

对于已经选取的一些系列数,记他们异或起来的值是A,和是S。
现在增加一个新的数(a>=0)A'=A^a,S'=S+a
由于涉及到异或,我们考虑二进制表示形式下的第k位,并且B(a,k)表示a的二进制的第k位的值。

考虑第k位

考虑A部分

  •     若B(n,i)=0,从A到A',第i位变化值为0.
  •     若B(n,i)=1,对A来说,该位取反。如果是0变1,则数变大了;如果1变0,则该位最多损失1.总结下来就是该位最多损失1.

考虑B部分

  •     若B(n,i)=0,S部分变化值为0.
  •     若B(n,i)=1,S部分变化值为增加1.
综合考虑A、B部分可以发现,增加一个数a,A+S的值不可能减少,只有可能不变,或者增加。
基于这个结论容易得出选取所有数值最大。


全部评论

相关推荐

头像
04-17 09:29
已编辑
湖南农业大学 后端
睡姿决定发型丫:本硕末9也是0offer,简历挂了挺多,只有淘天 美团 中兴给了面试机会,淘天二面挂,美团一面kpi面,中兴一面感觉也大概率kpi(虽然国企,但一面0技术纯聊天有点离谱吧)
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务