自动搬运

查看原文

来自洛谷，原作者为

	Anxiomgh NOIP 2023 RP++

搬运于2025-08-24 22:37:36，当前版本为作者最后更新于2022-04-10 21:40:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

蒟蒻的第一篇题解，请大家多多指教。

Sol

首先给出异或运算的三个性质：

1. 归零律：$a \oplus a = 0$
2. 恒等律：$a \oplus 0 = a$
3. 结合律：$a \oplus b \oplus c = a \oplus (b \oplus c) = (a \oplus b) \oplus c$

由题意得：
$p$ 是 $a$ 的前缀异或数组，满足 $p_i = \bigoplus_{j=1}^ia_j$

$s$ 是 $a$ 的后缀异或数组，满足 $s_i = \bigoplus_{j=i}^na_j$

根据 性质 1 和 性质 3，易得 引理 1:

$$a_i = p_i \oplus p_{i-1} = s_i \oplus s_{i+1}$$

也就是说，只要能还原出 $p$ 或 $s$ 数组中的每一个被换成 -1 的数的一个合法解，一定可以还原出数组 $a$ 的一个合法解。

如何还原呢？再观察一下数组 $p$ 和 $s$，根据 性质 2，不妨把 $p_0$ 和 $s_{n+1}$ 设为 0，设 $sum = \bigoplus_{i=1}^na_i$，根据 性质 3，易得 引理 2：

$$p_i \oplus s_{i+1} = sum(0 \leq i \leq n)$$

不难发现，如果用 引理 2 还原 $p$ 数组或 $s$ 数组，必定要先用 引理 2 求得 $sum$。因为根据题意，有条件 $\textstyle\sum[p_i = -1] + \textstyle\sum[s_i = -1] = n$($1 \leq i \leq n$)，所以可得 引理 3：

$$\exists i \in N(0 \leq i \leq n),p_i \neq -1,s_{i+1} \neq -1 $$

证明如下:

假设 $\forall i \in N(0 \leq i \leq n)$，$p_i$ 或 $s_{i+1}$ 中有一个值为 $-1$.

$\because$ $p_0 = s_{n+1} = 0$.

$\therefore$ 有 $\textstyle\sum[p_i = -1] + \textstyle\sum[s_i = -1] = n + 1(1 \leq i \leq n)$，与条件矛盾.

$\therefore$ 假设不成立.

引理 3 得证.

于是根据 引理 3 和 引理 2，$O(n)$ 遍历一遍两个数组可以求得 $sum$，再根据 引理 2，$O(n)$ 遍历一遍两个数组就可以还原两个数组的一组合法解。还原过程如下：
对于任意一对 $p_i$，$s_{i+1}$，分三种情况讨论:

1. $p_i$ 和 $s_{i+1}$ 都不为 $-1$，不做处理。
2. $p_i$ 和 $s_{i+1}$ 中有一个为 $-1$，用 $sum$ 异或另一个元素即可获得为 $-1$ 元素的值。
3. $p_i$ 和 $s_{i+1}$ 都为 $-1$，那么它们就没有确定的值。通过性质2可以发现，当把 $a_i$ 赋值为 $0$ 时，最易处理并且不违反任何条件。此时，$p_i = p_{i-1} \oplus 0 = p_{i-1}$，赋值完 $p_i$ 后，就变成了第2种情况，即可求得 $s_{i+1}$ 的值。

最后，根据 引理 1，遍历一遍 $p$ 数组或 $s$ 数组即可求得原数组的值。

时间复杂度 $O(\textstyle\sum n)$，即可通过本题。

代码

#include<iostream>

using namespace std;
#define ll long long //不要忘记开 ll 

ll p[100010];
ll s[100010];

ll find(int n) //查找 
{
	for (int i = 0; i <= n; i++)
		if (p[i] != -1 && s[i + 1] != -1)
			return p[i] ^ s[i + 1];
}

void update(ll val, int n) //还原 
{
	for (int i = 0; i <= n; i++)
	{
		if (p[i] != -1 && s[i + 1] == -1) 
			s[i + 1] = val ^ p[i];
		else if (p[i] == -1 && s[i + 1] != -1) 
			p[i] = val ^ s[i + 1];
		else if (p[i] == -1 && s[i + 1] == -1)
		{
			p[i] = p[i - 1];
			s[i + 1] = val ^ p[i];
		}
	}
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> p[i];
		for (int i = 1; i <= n; i++) cin >> s[i];
		
		ll sum = find(n); //查找所有数异或的结果，记为 sum 
		
		update(sum, n); //还原 p 数组和 s 数组 

		for (int i = 1; i <= n; i++)
			cout << (p[i] ^ p[i - 1]) << " "; //用 p 数组求原数组的值，也可以用 s 数组 
		cout << endl;
	}
	return 0;
}