小Q与彼岸花

NC219166. 小Q与彼岸花

描述

小 Q 的院子里种了 $n$ 朵彼岸花，其中第 $i$ 朵的彼岸花的美丽值为 $a_i$ ，彼岸花按照编号从小到大从左向右排成了一排。

现在小 Q 有 $m$ 个问题，他每次会给出一个区间 $[l,r]$ ，他想在编号属于区间 $[l,r]$ 的彼岸花中选出两朵花，使得 $a_i\bigoplus a_j$ ( $\bigoplus$ 表示按位异或操作) 的值最大（如果只能选出一朵花请直接输出 $0$ ）。

由于他太菜了，只能来问你了。

输入描述

第一行两个整数 。            
第二行  个整数，分别表示 。       
接下来  行，每行两个整数分别表示一个问题所给出的区间 。

输出描述

输出  行，表示每个问题的答案。

示例1

输入:

10 10
1 2 3 4 5 6 7 8 9 10
1 2
1 3
1 5
2 6
2 8
2 10
3 7
8 10
6 9
1 7

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 180ms, 内存消耗: 67520K, 提交时间: 2021-09-12 11:37:16

#include<bits/stdc++.h>
using namespace std;
int dp[5010][5010],a[5010],n,m,l,r;

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int len=1;len<=n;len++){
		for(int s=1;s+len-1<=n;s++){
			int t=s+len-1;
			dp[s][t]=max(a[s]^a[t],max(dp[s+1][t],dp[s][t-1]));
		}
	}
	
	while(m--){
		cin>>l>>r;
		cout<<dp[l][r]<<"\n";
	} 
	return 0;
}

上一题

下一题

详情