[C++知识库]D1. 388535 (Easy Version)（trie树）

Codeforces Round #779 (Div. 2)

Problem

Input

3
0 3
3 2 1 0
0 3
4 7 6 5
0 2
1 2 3

Output

0
4
3

Solution

（我只是把答案翻译了一下(￣▽￣)"）

首先观察一下 0 ~ 7的二进制字符串的特点

0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

让我们单独观察某一列。可以发现，当某一列的前缀长度为 2 的幂次时，0的数量和1的数量相同。其他情况 0 的数量 > 1的数量。因此，
当1的数量大于0时，x的对应列为 1
当0的数量大于1时，x的对应列为 0
当1的数量等于0时，x的对应列为 0 或 1
以上规律可以这样简单证明， 当 x 在数组a中时， x $\oplus$ 2ⁱ 也在数组a中。

最后就是算法实现过程，code实现是用的 trie 树，不明白的可以上 百度 查一下。

Code

int cnt[20][2];
void solve()
{
	mt(cnt, 0);
	int l, r; cin >> l >> r;
	for (int i = l, x; i <= r; i++)
	{
		cin >> x;
		for (int j = 0; j < 20; j++, x >>= 1)
			cnt[j][x & 1]++;
	}

	int ans = 0;
	for (int i = 0; i < 20; i++)
		ans |= (1 << i) * (cnt[i][1] > cnt[i][0]);

	cout << ans << endl;
}

int main()
{
	IOS;
	int T; cin >> T;
	while (T--)
	{
		solve();
	}

	return 0;
}