2017年院赛H题 最大异或和

2019-04-14 18:17发布

站内文章 / 模拟电子
12010 0 1189
目录： 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<=100000) 接下来一行输入n个正整数a0,a1,....,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; }

热门文章