题目链接

题目描述

给定一个长为 $n$ 的数列 $b_i$，要求构造一个长为 $n$ 的数列 $a_i$

$b_1 = a_1$

$b_i = a_i \oplus a_{i - 1}$

要求 $a_i$ 严格单调递增

$1 \le n \le 10^5$

$1 \le b_i \le 2^{60}$

简要做法

$a_i = b_1 \oplus \ldots \oplus b_i$

$a_i = a_{i - 1} \oplus b_i$

要使 $a_i > a_{i - 1}$

则 $b_i$ 的最高位在 $a_{i - 1}$ 中为 $0$

因为 $2^n > 2^1 + 2^2 + \ldots + 2^{n - 2} + 2^{n - 1}$

所以贪心即可

参考代码

#include <stdio.h>
#include <algorithm>
#include <memory.h>
#include <queue>

#define int long long

const int N = 1e5 + 5;
const int M = 60 +　５;

int n, ans[N];
std::queue<int> Q[M];

int read()
{
	int x = 0, f = 1;
	char ch = getchar();
	while ('0' > ch or ch > '9')
		f = ch == '-' ? -1 : 1, ch = getchar();
	while ('0' <= ch and ch <= '9')
		x = x * 10 + ch - 48, ch = getchar();
	return x * f;
}

signed main()
{
	n = read();
	for (int i = 1, x; i <= n; i++)
	{
		x = read();
		for (int j = 60, flag = 1; j >= 0 and flag; j--)
			if (x & (1 << j))
				Q[j].push(x), flag = 0;
	}
	for (int i = 1, flag = 1, x = 0; i <= n; i++, flag = 1)
	{
		for (int j = 0; j <= 60 and flag; j++)
			if (!(x & (1LL << j)) and !Q[j].empty())
				x ^= (ans[i] = Q[j].front()), Q[j].pop(), flag = 0;
		if (flag)
			return puts("No"), 0;
	}
	puts("Yes");
	for (int i = 1; i <= n; i++)
		printf("%I64d ", ans[i]);
	return 0;
}