2017年院試合H問題最大異和

目次:
2017年院試合A題Neptune'Pudding
2017年院試合B題N個数求和
2017年院試合C題treat
2017年の院試合D問題の簡単な暗号化
2017年の院試合E題守望者の脱出
2017年院試合F題数独ゲーム
2017年院試合G題忠誠
2017年院試合H問題最大異和
タイトル:
最大異和
 
Description:
AさんはBさんに一連の数字の中で連続した数字と最大を見つける問題を解決しました.Bさんがこのような簡単な問題に限らず、一反三を挙げることができるように、AさんはBさんに同じ理屈でどのように連続した数字を見つけることができますか.
 
Input:
サンプル群数正の整数Tを入力(T<=1000)
各サンプル群に正の整数nを入力し、数字の個数を表す(n<=10000000)
次の行にはn個の正の整数a 0,a 1,...,a(n-1)(任意ai<2^31)
 
Output:
各サンプルのセットは、答えが最大の異和を表す値を出力します.
 
Sample Input:
2
3
4 8 5
3
4 8 16
 
Sample Output:
13
28
スレッド:

#include 
#include 
#include 
using namespace std;
#define max(a,b) a>b?a:b
int bit[32];

struct Node{
    Node *lson,*rson;
    Node(){lson=rson=NULL;}
}*root;

void init()
{
    root = new Node(); bit[0] = 1;
    for(int i=1 ; i<32 ; i++) bit[i] = bit[i-1]<<1;
}

void insert(int x)
{
    Node *cur = root;
    for(int i=31 ; i>=0 ; i--){
        if(bit[i]&x){
            if(!cur->rson) cur->rson = new Node();
            cur = cur->rson;
        }else{
            if(!cur->lson) cur->lson = new Node();
            cur = cur->lson;
        }
    }
}

int match(int x)
{
    Node *cur = root;
    int ans = 0;
    for(int i=31 ; i>=0 ; i--){
        if(bit[i]&x){
            if(cur->lson) cur = cur->lson , ans = ans|bit[i];
            else cur = cur->rson;
        }else{
            if(cur->rson) cur = cur->rson , ans = ans|bit[i];
            else cur = cur->lson;
        }
    }
    return ans;
}

int main()
{
    int n , x , cur , T , ans;
    scanf("%d" , &T);
    while(T--){
        init();
        insert(0); ans = cur = 0;
        scanf("%d" , &n);
        for(int i=0 ; i<n ; i++){
            scanf("%d" , &x);
            cur = cur^x ;
            ans = max(ans , match(cur));
            insert(cur);
        }
        printf("%d
" , ans);
    }
    return 0;
}