列表

详情


NC20005. [HEOI2013]ALO

描述

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 
现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量密度两两不同。
现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为  ai, ai+1, …, aj,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为k,则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。
现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

输入描述

第一行,一个整数 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;
}

上一题