All RE 求调
查看原帖
All RE 求调
392616
Lobri__楼主2022/9/28 20:22

大概率是 q 出了问题,不过机房几个人一起找也没招出来,本地第一组数据 AC,不过在 oj 上 re 了。

#include <iostream>
#include <queue>
#define int long long
using namespace std;

const int MAXN = 2e7 + 7;
int a[MAXN], s[MAXN], trie[MAXN][2], size[MAXN];
int n, k, ans, tot;
int _end[MAXN];

struct node
{
	int x, y, w;
	bool operator <(const node &a)const
	{
		return w < a.w;
	}
};

priority_queue<node> q;

void insert(int x)
{
	int u = 0;
	for (int i = 31; i >= 0; i --)
	{
		int ch = (x >> i) & 1;
		if (!trie[u][ch])
			trie[u][ch] = ++ tot;
//		cout << u << ' ' << ch << ' ' << trie[u][ch]  << endl;
		u = trie[u][ch];
		size[u] ++;
	}
	_end[u] ++;
}

int query(int x, int t)
{
	int u = 0, res = 0;
	for (int i = 31; i >= 0; i --)
	{
		bool ch = (x >> i) & 1;
        if(t <= size[trie[u][ch ^ 1]]) ch ^= 1;
        else t -= size[trie[u][ch ^ 1]];
//		cout << u << ' ' << ch << ' ' << trie[u][ch] << ' ' << size[trie[u][ch]] << ' ';
		u = trie[u][ch];
		res <<= 1, res |= ch;
//		cout << res << endl;
	}
	return res ^ x ;
}

signed main()
{
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
	{
		cin >> a[i];
		s[i] = s[i - 1] ^ a[i];
	}

	for (int i = 0; i <= n; i ++)
	{
		insert(s[i]);
	}
	
//	cout << endl;
//	for (int i = 0; i <= n; i ++) cout << s[i] << ' ';
//	cout << endl << endl;
	
//	query(3, 2);
//	return 0;
	
	for (int i = 0; i <= n; i ++)
	{
		int w = query(s[i], 1);
		q.push((node){i, 1, w});
	}
	
//	for (int i = 1; i <= n; i ++)
//	{
//		for (int j = 1; j < n; j ++)
//		{
//			cout << s[i] << ' ' << j << ' ' << query(s[i], j) << endl;;
//		}
//	}
//	cout << endl << endl;


	int ans = 0;
	k *= 2;
	
	while (k --)
	{
		node t = (node){1, 1, 1};
		if(q.size())
		{
			t = q.top();
			q.pop();
		}
		
		ans += t.w;
//		cout << s[t.x] << ' ' << t.y << ' ' << t.w << ' ' << ans << endl;
		t.y ++;
		if(t.y < n) 
		{
			t.w = query(s[t.x], t.y);
//			cout << s[t.x] << ' ' << t.y << ' ' << t.w << endl;
			q.push(t);
		}
	}
	
	cout << ans / 2;
	
	return 0;
}

2022/9/28 20:22
加载中...