LightOJ 1269 Consecutive Sum （Trie树）

Jan's LightOJ :: Problem 1269 - Consecutive Sum

　　题意是，求给定序列的中，子序列最大最小的抑或和。

　　做法就是用一棵Trie树，记录数的每一位是0还是1。查询的时候，如果求最大值，就尽量让高位是1，相反就尽量让高位是0。

代码如下，1y：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 using namespace std;

 const int N = ;

 const int M = ;

 struct Node {

     int c[];

     void init() { c[] = c[] = -;}

 } ;

 struct Trie {

     Node node[M * N];

     int rt, curid;

     void init() { rt = curid = ; node[curid++].init();}

     void insert(int x, int dg = ) {

         int p = rt;

         for (int i = dg - , idx; i >= ; i--) {

             idx = (x &  << i) != ;

             if (node[p].c[idx] == -) node[node[p].c[idx] = curid++].init();

             p = node[p].c[idx];

         }

     }

     int min(int x, int dg = ) {

         int p = rt, ret = ;

         for (int i = dg - , idx; i >= ; i--) {

             idx = (x &  << i) != ;

             if (~node[p].c[idx]) p = node[p].c[idx], ret <<= , ret |= idx;

             else p = node[p].c[!idx], ret <<= , ret |= !idx;

         }

         return ret;

     }

     int max(int x, int dg = ) {

         int p = rt, ret = ;

         for (int i = dg - , idx; i >= ; i--) {

             idx = (x &  << i) == ;

             if (~node[p].c[idx]) p = node[p].c[idx], ret <<= , ret |= idx;

             else p = node[p].c[!idx], ret <<= , ret |= !idx;

         }

         return ret;

     }

 } trie;

 int main() {

     int T, n, x;

     scanf("%d", &T);

     for (int cas = ; cas <= T; cas++) {

         scanf("%d", &n);

         int ans1 = 0x80000000, ans2 = 0x7fffffff, sum = ;

         trie.init();

         trie.insert();

         for (int i = ; i < n; i++) {

             scanf("%d", &x);

             sum ^= x;

             //cout << sum << endl;

             ans1 = max(ans1, trie.max(sum) ^ sum);

             ans2 = min(ans2, trie.min(sum) ^ sum);

             trie.insert(sum);

         }

         printf("Case %d: %d %d\n", cas, ans1, ans2);

     }

     return ;

 }

　　其实做这题的时候想到一种比较麻烦的情况，那就是数里面有负数。这样的话需要对最高位特判，从而求得最大最小值。不过没有这样的数据，所以就不这么搞了。

——written by Lyon