NC20005. [HEOI2013]ALO
描述
输入描述
第一行,一个整数 n,表示宝石个数。第二行, n个整数,分别表示a1至an,表示每颗宝石的能量密度,保证对于i ≠ j有 ai ≠ aj。
输出描述
输出一行一个整数,表示最大能生成的宝石能量密度。
示例1
输入:
5 9 2 1 4 7
输出:
14
C++ 解法, 执行用时: 173ms, 内存消耗: 20384K, 提交时间: 2022-07-16 18:42:02
#include<bits/stdc++.h> using namespace std; const int N=5e4; const int M=2e7; const int mod=1e9+7; const long long INF=0x3f3f3f3f3f3f3f3fLL; int n,a[N+10],rt[N+10],tot; int L[N+10],R[N+10],ans; pair<int,int>b[N+10]; struct Trie{ int son[2]; int sum; }trie[(N+10)<<5]; void build(int val,int id){ rt[id]=++tot; int y=rt[id-1],x=rt[id]; trie[x].sum=trie[y].sum+1; for(int i=30;i>=0;i--){ int c=(val>>i)&1; trie[x].son[c^1]=trie[y].son[c^1]; trie[x].son[c]=++tot; x=trie[x].son[c],y=trie[y].son[c]; trie[x].sum=trie[y].sum+1; } } int query(int l,int r,int val){ if(l>r)return 0; l=rt[l-1],r=rt[r]; int tmp=0; for(int i=30;i>=0;i--){ int c=(val>>i)&1; if(trie[trie[r].son[c^1]].sum>trie[trie[l].son[c^1]].sum) tmp|=(1<<i),l=trie[l].son[c^1],r=trie[r].son[c^1]; else l=trie[l].son[c],r=trie[r].son[c]; } return tmp; } int main(){ ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; build(a[i],i); b[i]=make_pair(a[i],i); L[i]=i-1,R[i]=i+1; } sort(b+1,b+1+n); for(int i=1;i<=n;i++){ int id=b[i].second; int l=L[id],r=R[id]; L[r]=l,R[l]=r; if(l)ans=max(ans,query(L[l]+1,r-1,a[id])); if(r)ans=max(ans,query(l+1,R[r]-1,a[id])); } cout<<ans; return 0; }