萌新初学救一救(SOS)dp求调
查看原帖
萌新初学救一救(SOS)dp求调
490978
小超手123楼主2024/3/13 18:31
#include<bits/stdc++.h>
#define int long long
#define N 5000006 
using namespace std;
int n, m = 22, ans;
int a[N];
int g[N], f[N]; //次大值,最大值 
int Get(int x) {
	return ((1 << m) - 1) ^ x;
} 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		
		int x = Get(a[i]);
		//cout << a[i] << endl;
		if(i >= f[x]) {
			g[x] = f[x];
			f[x] = i;
		}
		else if(i >= g[x]) g[x] = i;
	} 
//	for(int i = 1; i <= n; i++) cout << a[i] << endl;
	for(int i = 0; i < m; i++)
	for(int j = 0; j < (1 << m); j++) {
		if(j & (1 << i)) {
			int now = f[j ^ (1 << i)];
			if(now >= f[j]) {
				g[j] = f[j];
				f[j] = now;
			}
			else if(now >= g[j]) g[j] = now;
		}
	}
	//for(int i = 1; i <= n; i++) cout << a[i] << endl;
	for(int i = 1; i <= n; i++) {
		//cout << a[i] << endl;
		int res = 0, B = 0;
		for(int j = m - 1; j >= 0; j--) {
			if(a[i] & (1 << j)) {
				res += (1 << j);
				continue;
			}
			if(i < g[Get(B + (1 << j))]) {
				res += (1 << j);
				B += (1 << j);
			}
		}
		ans = max(ans, res);
	}
	cout << ans;
	return 0;
}







2024/3/13 18:31
加载中...