Codeforces Round #173 (Div. 2) E. Sausage Maximization Trie

链接：

http://codeforces.com/contest/282/problem/E

题意：

给你一个数组，让你取一个不相交的前缀和后缀（可以为空），使它们的异或和最大

题解：

当然是先求出前缀异或和和后缀异或和，先把所有的后缀异或和插入到Trie中，然后枚举每一个前缀，先更新后缀，再查找最大的，更新结果即可

这个Trie字典树开小了 re了两发。。

代码：

31 int n;
32 ll a[MAXN];
33 ll pre[MAXN], suf[MAXN];
34 int Trie[MAXN * 100][2], V[MAXN * 100];
35 int sz = 1;
36 
37 void insert(string s, int val) {
38     int now = 1;
39     rep(i, 0, s.length()) {
40         int x = s[i] - '0';
41         if (!Trie[now][x]) Trie[now][x] = ++sz;
42         now = Trie[now][x];
43         V[now] += val;
44     }
45 }
46 
47 ll query(string s) {
48     int now = 1;
49     string res;
50     rep(i, 0, s.length()) {
51         int x = s[i] - '0';
52         x ^= 1;
53         if (V[Trie[now][x]]) res += x + '0', now = Trie[now][x];
54         else res += x ^ 1 + '0', now = Trie[now][x ^ 1];
55     }
56     return bitset<50>(res).to_ullong();
57 }
58 
59 int main() {
60     ios::sync_with_stdio(false), cin.tie(0);
61     cin >> n;
62     rep(i, 1, n + 1) cin >> a[i];
63     pre[1] = a[1];
64     rep(i, 2, n + 1) pre[i] = pre[i - 1] ^ a[i];
65     suf[n] = a[n];
66     per(i, 1, n) suf[i] = suf[i + 1] ^ a[i];
67     rep(i, 0, n + 2) {
68         string s = bitset<50>(suf[i]).to_string();
69         insert(s, 1);
70     }
71     ll ans = 0;
72     rep(i, 0, n + 2) {
73         ll sum = pre[i];
74         string a = bitset<50>(pre[i]).to_string();
75         string b = bitset<50>(suf[i]).to_string();
76         insert(b, -1);
77         sum ^= query(a);
78         ans = max(ans, sum);
79     }
80     cout << ans << endl;
81     return 0;
82 }