[原创]华中农业大学第五届程序设计大赛 H MathematicalGame [01字典树]【字典树】

2017-05-26 21:55:54 Tabris_ 阅读数：467

博客爬取于2020-06-14 22:40:31
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72773955

题目链接：http://acm.hzau.edu.cn/problem.php?id=1206
——————————————————————————————————————
1206: MathematicalGame
Time Limit: 2 Sec Memory Limit: 1280 MB
Submit: 170 Solved: 26
[Submit][Status][Web Board]
Description
Xiao Ming likes to play mathematical games very much. One day, he gets a sequence of n positive integers. XOR (l , r) is defined as the XOR and of all numbers in a continuous interval. Now, Xiao Ming wants to know the intervals which make the XOR (l , r) become largest.

Require l, r.

Input
There is an integer T at the first line, indicate the case of data.

In each case, there is an integer N at the first line, indicate the length of the sequence. And there are N integers, a1, a2, … , an, at the second line. (N <= 1,000,000)

Output
In each case, the first line is “Case #k:”, k is the number of test cases, the next line includes two integers l and r, which separated by a space.

l, r output in lexicographic order if there are multiple results.

Sample Input
1
5
1 2 3 4 5
Sample Output
Case #1:
3 4

————————————————————————————————————————
题目大意：
问你区间异或值最大的区间是多少，如果值有多个，输出字典序最小的那个

解题思路:

相信大家都会 区间内选两个值，异或最大

那么这个也一样，只要维护的是前缀异或和就好了，这样就变成了经典问题。

然后维护结果就好了

附本题代码
——————————————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2e6+7;
//const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x;
}
/*******************************************/

int n,a,x;
int trie[N*31][2],val[N*31],cnt;

int l,r,mx;

void inserttrie(int x,int id){
    int now=0,bt;
    for(int i=30;i>=0;i--){
        bt = (x&(1<<i))?1:0;
        if(!trie[now][bt]) trie[now][bt] = ++cnt;
        now=trie[now][bt];
    }
    if(-1==val[now]) val[now]=id;
}

int ask(int x,int y){
//    printf("%d ->" ,x);
    int now=0,bt,v=0;
    for(int i=30;i>=0;i--){
        bt = (x&(1<<i))?1:0;
//printf("%d",bt);
        if(trie[now][1-bt]) bt=1-bt,v|=(1<<i);


        now=trie[now][bt];
    }
//    puts("    <-");
    int vn = val[now]+1;
//    printf("%d %d\n",v,mx);
    if(v>mx) mx=v,l=vn,r=y;
    if(v==mx){if(vn<l||vn==l&&y<r)l=vn,r=y;}
}

int main(){
    memset(trie,0,sizeof(trie));
    memset(val,-1,sizeof(val));

    int _,kcase = 0;
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);l=r=1;
        a=0;cnt=0;mx=0;
        inserttrie(a,0);
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            a^=x;
//            printf("%d%c",a,(i==n)?'\n':' ');
            ask(a,i);
            inserttrie(a,i);
        }
        printf("Case #%d:\n",++kcase);
        printf("%d %d\n",l,r);

        for(int i=0;i<=cnt;i++){
            trie[i][0]=trie[i][1]=0;
            val[i]=-1;
        }
    }
    return 0;
}