CF1777F 那题,本机过 #1,提交 RE on #1
查看原帖
CF1777F 那题,本机过 #1,提交 RE on #1
232838
huangkx楼主2023/1/24 09:17

RT,代码不长,不知道哪里挂了,求大佬帮忙看看,谢谢。

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
int ans;
int a[N + 1], sum[N + 1];
struct Trie{
	vector < int > ch[2];
	int Create_Node()
	{
		ch[0].push_back(0), ch[1].push_back(0);
		return ch[0].size() - 1;
	}
	Trie()
	{
		Create_Node();
	}
	void Insert(int x)
	{
		for(int i = 20, u = 0; i >= 0; i --){
			if(ch[!! (x & (1 << i))][u] == 0) ch[!! (x & (1 << i))][u] = Create_Node();
			u = ch[!! (x & (1 << i))][u];
		}
	}
	int Query(int x)
	{
		int res = 0;
		for(int i = 20, u = 0; i >= 0; i --){
			if(ch[! (x & (1 << i))][u]) res += (1 << i), u = ch[! (x & (1 << i))][u];
			else u = ch[!! (x & (1 << i))][u];
		}
		return res;
	}
};
Trie tr[2][N + 1];
int DFS(int l, int r)
{
	if(l > r) return 0;
	if(l == r) return l;
	int maxn = - 1e9, p = 0;
	for(int i = l; i <= r; i ++) if(a[i] > maxn) maxn = a[i], p = i;
	int pl = DFS(l, p - 1), pr = DFS(p + 1, r);
	if(p - l < r - p){
		tr[0][pr].Insert(sum[p - 1]), tr[1][pr].Insert(sum[p]);
		for(int i = l; i <= p; i ++) ans = max(ans, tr[1][pr].Query(sum[i - 1] ^ a[p]));
		for(int i = l; i <= p - 1; i ++) tr[0][pr].Insert(sum[i - 1]), tr[1][pr].Insert(sum[i]);
		return pr;
	}else{
		tr[0][pl].Insert(sum[p - 1]), tr[1][pl].Insert(sum[p]);
		for(int i = p; i <= r; i ++) ans = max(ans, tr[0][pl].Query(sum[i] ^ a[p]));
		for(int i = p + 1; i <= r; i ++) tr[0][pl].Insert(sum[i - 1]), tr[1][pl].Insert(sum[i]);
		return pl;
	}
}
void solve()
{
	ans = 0;
	int n; scanf("%d", & n);
	for(int i = 1; i <= n; i ++) scanf("%d", & a[i]);
	for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] ^ a[i];
	for(int i = 1; i <= n; i ++) tr[0][i].Insert(sum[i - 1]), tr[1][i].Insert(sum[i]);
	DFS(1, n);
	printf("%d\n", ans);
}
int main()
{
	int t; scanf("%d", & t);
	while(t --) solve();
	return 0;
}
2023/1/24 09:17
加载中...