LightOJ 1269 - Consecutive Sum(字典树) - c++编程基础

题目大意：给定一个序列，选定一段区间的亦或和，输出最大和最小。

解题思路：最大很简单，对所有前缀建立字典树，然后尽量往反向走；最小则需要往正向走，并且向正向走的时候要扣

除自己本身。

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int maxn = 50005 * 32; const int sigma_size = 2; struct Tire { int sz; int g[maxn][sigma_size]; int c[maxn]; void init(); void insert(int s); int findMax(int s); int findMin(int s); }T; int N, A[maxn]; int main () { int cas, x; scanf("%d", &cas); for (int kcas = 1; kcas <= cas; kcas++) { T.init(); scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &x); A[i] = A[i-1] ^ x; } for (int i = 0; i <= N; i++) T.insert(A[i]); int ansMax = 0, ansMin = (1<<31)-1; for (int i = 0; i <= N; i++) { ansMax = max(ansMax, T.findMax(A[i])); ansMin = min(ansMin, T.findMin(A[i])); } printf("Case %d: %d %d\n", kcas, ansMax, ansMin); } return 0; } void Tire::init() { sz = 1; c[0] = 0; memset(g[0], 0, sizeof(g[0])); } int Tire::findMin(int s) { int ret = 0, u = 0; for (int i = 30; i >= 0; i--) { int v = (s>>i) & 1; if (g[u][v] == 0 || (g[u][v^1] && c[g[u][v]] < 2)) { v = v ^ 1; ret |= (1<
      
       = 0; i--) { int v = ((s>>i)&1)^1; if (g[u][v]) ret |= (1<
       
        = 0; i--) { int v = (s>>i) & 1; if (g[u][v] == 0) { c[sz] = 0; memset(g[sz], 0, sizeof(g[sz])); g[u][v] = sz++; } u = g[u][v]; c[u]++; } }