首页 > 代码库 > BZOJ3166: [Heoi2013]Alo
BZOJ3166: [Heoi2013]Alo
3166: [Heoi2013]Alo
Time Limit: 20 Sec Memory Limit: 256 MBSubmit: 394 Solved: 204
[Submit][Status]
Description
Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG ，
如名字所见，到处充满了数学的谜题。
现在你拥有n颗宝石，每颗宝石有一个能量密度，记为ai，这些宝石的能量
密度两两不同。现在你可以选取连续的一些宝石（必须多于一个）进行融合，设为 ai, ai+1, …, a j，则融合而成的宝石的能量密度为这些宝石中能量密度的次大值
与其他任意一颗宝石的能量密度按位异或的值，即，设该段宝石能量密度次大值
为k，则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。
现在你需要知道你怎么选取需要融合的宝石，才能使生成的宝石能量密度最大。
Input
第一行，一个整数 n，表示宝石个数。
第二行， n个整数，分别表示a1至an，表示每颗宝石的能量密度，保证对于i ≠ j有 ai ≠ aj。
Output
输出一行一个整数，表示最大能生成的宝石能量密度。
Sample Input
5
9 2 1 4 7
9 2 1 4 7
Sample Output
14
HINT
【样例解释】
选择区间[1,5]，最大值为 7 xor 9。
对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9
Source
加强型数据By Hta
题解：
枚举这个次小值，那么它作为最小值的区间就是左边第二个比它大的数的位置+1到右边第二个比它大的数的位置-1，这一步可以用set（我刚开始居然用的单调队列。。。）
然后可持久化trie搞就行了
代码：
View Code
枚举这个次小值，那么它作为最小值的区间就是左边第二个比它大的数的位置+1到右边第二个比它大的数的位置-1，这一步可以用set（我刚开始居然用的单调队列。。。）
然后可持久化trie搞就行了
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm> 10 11 #include<iostream> 12 13 #include<vector> 14 15 #include<map> 16 17 #include<set> 18 19 #include<queue> 20 21 #include<string> 22 23 #define inf 1000000000 24 25 #define maxn 100000+5 26 27 #define maxm 2000000+5 28 29 #define eps 1e-10 30 31 #define ll long long 32 33 #define pa pair<int,int> 34 35 #define for0(i,n) for(int i=0;i<=(n);i++) 36 37 #define for1(i,n) for(int i=1;i<=(n);i++) 38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++) 40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--) 42 43 #define mod 1000000007 44 45 using namespace std; 46 47 inline int read() 48 49 { 50 51 int x=0,f=1;char ch=getchar(); 52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();} 56 57 return x*f; 58 59 } 60 int n,mx,l[maxn],r[maxn],a[maxn],tot,sta[maxn],rt[maxn],t[maxm][2],id[maxm]; 61 pair<int,int>b[maxn]; 62 set<int>s; 63 set<int>::iterator it; 64 inline void insert(int pre,int x,int k) 65 { 66 int now=rt[k]=++tot;id[tot]=k; 67 for3(i,30,0) 68 { 69 int j=(x>>i)&1; 70 t[now][j^1]=t[pre][j^1]; 71 t[now][j]=++tot;id[tot]=k; 72 now=tot; 73 pre=t[pre][j]; 74 } 75 } 76 inline int query(int l,int r,int x) 77 { 78 int now=rt[r],ret=0; 79 for3(i,30,0) 80 { 81 int j=((x>>i)&1)^1; 82 if(id[t[now][j]]>=l)ret|=1<<i;else j^=1; 83 now=t[now][j]; 84 } 85 return ret; 86 } 87 inline int getl(int x) 88 { 89 it=s.find(x); 90 if(it--==s.begin())return 0; 91 if(it--==s.begin())return 0; 92 return *it; 93 } 94 inline int getr(int x) 95 { 96 it=s.find(x); 97 if(++it==s.end())return n+1; 98 if(++it==s.end())return n+1; 99 return *it;100 }101 102 int main()103 104 {105 106 freopen("input.txt","r",stdin);107 108 freopen("output.txt","w",stdout);109 n=read();id[0]=-1;110 insert(rt[0],0,0);111 for1(i,n)112 {113 a[i]=read();insert(rt[i-1],a[i],i);mx=max(mx,a[i]);114 b[i].first=a[i];b[i].second=i;115 }116 sort(b+1,b+n+1);117 for3(i,n,1)118 {119 s.insert(b[i].second);120 l[b[i].second]=getl(b[i].second);121 r[b[i].second]=getr(b[i].second);122 }123 int ans=0;124 for1(i,n)if(a[i]!=mx)ans=max(ans,query(l[i]+1,r[i]-1,a[i]));125 printf("%d\n",ans);126 127 return 0;128 129 }
BZOJ3166: [Heoi2013]Alo
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。