1414. 牛异或

题目链接:https://www.acwing.com/problem/content/description/1416/

思路:任意一段可以通过前缀和转换成两个点的最大值

那么就变成了最简单的trie求一对 数 的最大异或了,然后要求左边界最大,有边界最小

只需要 保留第一个答案 并且更新的时候直接覆盖掉即可

1414. 牛异或
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=998244353;
 5 #define ll long long
 6 #define ull unsigned long long
 7 #define pi pair<int,int>
 8 #define fi first
 9 #define sc second
10 #define pb push_back
11 int a[maxn];
12 int trie[maxn*22][2];
13 int id[maxn*22];
14 int tot;
15 
16 void add(int x,int k)
17 {
18     int p=0;
19     for(int i=21;i>=0;i--)
20     {
21         int u=(x>>i)&1;
22         if(!trie[p][u]) trie[p][u]=++tot;
23         p=trie[p][u];
24     }
25     id[p]=k;
26 }
27 
28 int query(int x)
29 {
30     int p=0;
31     for(int i=21;i>=0;i--)
32     {
33         int u=(x>>i)&1;
34         if(trie[p][!u]) p=trie[p][!u];
35         else p=trie[p][u];
36     }
37     return id[p];
38 }
39 
40 
41 
42 
43 
44 int main()
45 {
46     ios::sync_with_stdio(0);
47     cin.tie(0);
48     int n;
49     cin>>n;
50     for(int i=1;i<=n;i++)
51     {
52         cin>>a[i];
53         a[i]^=a[i-1];
54     }
55     int ans=-1,l=-1,r=-1;
56     add(0,0);
57     for(int i=1;i<=n;i++)
58     {
59         int p=query(a[i]);
60         int tmp=a[i]^a[p];
61         if(tmp>ans) ans=tmp,l=p+1,r=i;
62         add(a[i],i);
63     }
64     cout<<ans<<" "<<l<<" "<<r<<'\n';
65 
66 
67 
68 }
View Code

 

上一篇:算法总结篇---字典树(Trie)


下一篇:leetcode208. 实现 Trie (前缀树)