问题 5254 --6.1.3 Cow XOR (cowxor)

5254: 6.1.3 Cow XOR (cowxor)

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

6.1.3 Cow XOR (cowxor)

(cowxor.pas/c/cpp)

  农民约翰在喂奶牛的时候被另一个问题卡住了。他的所有N(1 <= N <= 100,000)个奶牛在他面前排成一行(按序号1..N的顺序),按照它们的社会等级排序。奶牛#1有最高的社会等级,奶牛#N最低。每个奶牛同时被指定了一个不唯一的附加值,这个数在0..2^21 - 1的范围内。

帮助农民约翰找出应该从哪一头奶牛开始喂,使得从这头奶牛开始的一个连续的子序列上,奶牛的附加值的异或最大。

如果有多个这样的子序列,选择结尾的奶牛社会等级最高的。如果还不唯一,选择最短的。


PROGRAM NAME: cowxor

INPUT FORMAT:

(file cowxor.in)

INPUT FORMAT

第1行:一个单独的整数N。

第2到N + 1行:N个0..2^21 - 1之间的整数,代表每头奶牛的被赋予的数。第j行描述了社会等级j - 1的奶牛。

OUTPUT FORMAT:

(file cowxor.out)

第 1 行: 3个空格隔开的整数,分别为:最大的异或值,序列的起始位置、终止位置。 时限0.5秒

SAMPLE INPUT

5
1
0
5
4
2

SAMPLE OUTPUT

6 4 5

样例输出说明

最大异或值为6,从第4个开始喂,到第5个结束。

4 异或 2 = 6

(100) 异或 (010) = (110)


来源

 

[提交][状态]