Jan's LightOJ :: Problem 1269 - Consecutive Sum

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

　　做法就是用一棵Trie樹，記錄數的每一位是0還是1。查詢的時候，如果求最大值，就盡量讓高位是1，相反就盡量讓高位是0。

代碼如下，1y：

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 8 const int N = 55555; 9 const int M = 32; 10 11 struct Node { 12 int c[2]; 13 void init() { c[0] = c[1] = -1;} 14 } ; 15 16 struct Trie { 17 Node node[M * N]; 18 int rt, curid; 19 void init() { rt = curid = 0; node[curid++].init();} 20 void insert(int x, int dg = 32) { 21 int p = rt; 22 for (int i = dg - 1, idx; i >= 0; i--) { 23 idx = (x & 1 << i) != 0; 24 if (node[p].c[idx] == -1) node[node[p].c[idx] = curid++].init(); 25 p = node[p].c[idx]; 26 } 27 } 28 int min(int x, int dg = 32) { 29 int p = rt, ret = 0; 30 for (int i = dg - 1, idx; i >= 0; i--) { 31 idx = (x & 1 << i) != 0; 32 if (~node[p].c[idx]) p = node[p].c[idx], ret <<= 1, ret |= idx; 33 else p = node[p].c[!idx], ret <<= 1, ret |= !idx; 34 } 35 return ret; 36 } 37 int max(int x, int dg = 32) { 38 int p = rt, ret = 0; 39 for (int i = dg - 1, idx; i >= 0; i--) { 40 idx = (x & 1 << i) == 0; 41 if (~node[p].c[idx]) p = node[p].c[idx], ret <<= 1, ret |= idx; 42 else p = node[p].c[!idx], ret <<= 1, ret |= !idx; 43 } 44 return ret; 45 } 46 } trie; 47 48 int main() { 49 int T, n, x; 50 scanf("%d", &T); 51 for (int cas = 1; cas <= T; cas++) { 52 scanf("%d", &n); 53 int ans1 = 0x80000000, ans2 = 0x7fffffff, sum = 0; 54 trie.init(); 55 trie.insert(0); 56 for (int i = 0; i < n; i++) { 57 scanf("%d", &x); 58 sum ^= x; 59 //cout << sum << endl; 60 ans1 = max(ans1, trie.max(sum) ^ sum); 61 ans2 = min(ans2, trie.min(sum) ^ sum); 62 trie.insert(sum); 63 } 64 printf("Case %d: %d %d\n", cas, ans1, ans2); 65 } 66 return 0; 67 } View Code

?

　　其實做這題的時候想到一種比較麻煩的情況，那就是數里面有負數。這樣的話需要對最高位特判，從而求得最大最小值。不過沒有這樣的數據，所以就不這么搞了。

?

——written by Lyon

轉載于:https://www.cnblogs.com/LyonLys/p/LOJ_1269_Lyon.html

總結

以上是生活随笔為你收集整理的LightOJ 1269 Consecutive Sum （Trie树）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。