2013级新生程序设计基础竞赛-正式赛 F 异或最大值 解题报告

F - 异或最大值

Time Limit: 2000/1000MS (Java/Others)      Memory Limit: 128000/64000KB (Java/Others)

Submit Status

Problem Description

小布除了经常能在野外遇到不明生物外还非常喜欢由非负数组成的数组, 有一天他的获得了一个由n个非负数组成的数组

而小布想在数组中找到一段连续的数字,使得这段数字异或起来的值是最大的

例如这个数组是  1, 2, 5, 7, 8

那么 (2,5,7) 是一段连续的数字, 这段数字异或起来的值为 2 ^ 5 ^ 7 = 0

(1, 2) 也是一段连续的数字,这段数字异或起来的值为 1 ^ 2 = 3

其中异或起来最大的连续数字段为 (7,8) 值为 7 ^ 8 = 15

Input

输入数据第一行是一个整数 T, 接下来有 T个例子

每个例子第一行是一个整数 n, 接下来是n个小于等于1000的非负整数 ( 1 <= n <= 100)

Output

对于每个例子输出 异或起来的值最大的 那个连续的数字段 异或起来的值

Sample Input

3
1
1
2
2 3
5
1 2 5 7 8

Sample Output

1
3
15

  为了找回做题的感觉- -......堪称暴力的经典～～～

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int maxn = 100 + 10;
int a[maxn];

int main()
{
    int T, n;
    while (scanf("%d", &T) != EOF)
    {
        while (T--)
        {
            scanf("%d", &n);
            for (int i = 0; i < n; i++)
                scanf("%d", &a[i]);
            int ans = a[0];
            for (int i = 0; i < n; i++)
            {
                int tmp = a[i];
                for (int j = i+1; j < n; j++)
                {
                    tmp ^= a[j];
                    ans = max(tmp, ans);  // 枚举所有长度（>= 2）的异或结果
                }
                ans = max(tmp, ans);  // 这个是关键啊～～，有可能单独的一个数就是最大的异或结果
            }
            printf("%d
", ans);
        }
    }
    return 0;
}