#J3047. 挑纸袋
挑纸袋
题目描述
假设你有n个纸袋,每个纸袋都有一个编号,将这些纸袋按照编号大小升序依次放在地上,然后按顺序每个纸袋放入一个价值为wi的小物品。现在,你可以从中挑选最少1个,最多n个纸袋,需要注意被挑选的这些纸袋编号必须是连续的。显然,关于纸袋的挑选有多种方案,问在所有的纸袋挑选方案里,被挑选纸袋的物品价值的异或之和最大是多少?输入格式
输入共2行。第1行是一个正整数n,表示总共有n个纸袋。
第2行有n个非负整数,第i个非负整数表示第i个纸袋里的物品价值为wi。
输出格式
输出在所有挑选方案中,被挑选纸袋的物品价值的异或之和的最大值。3
1 2 77
提示
样例解释:我们列出所有的选取方案:
(1) 只选编号为1的纸袋,价值的异或之和为1
(2) 只选编号为2的纸袋,价值的异或之和为2
(3) 只选编号为3的纸袋,价值的异或之和为7
(4) 选择编号为1和2这两个纸袋,其价值的异或之和为1^2=3
(5) 选择编号为2和3这两个纸袋,其价值的异或之和为2^7=5
(6) 选择编号为1、2、3的纸袋,其价值的异或之和为1^2^7=4
所以,在所有选取方案中,方案(3)的价值异或之和最大。
数据约定:
对于100%的数据:
1 ≤ n ≤ 100
0 ≤ wi < 230