P8279 「MCOI-08」【B】Fill In REMATCH 题解

· · 题解

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

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.

$\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$，不做处理。 1. $p_i$ 和 $s_{i+1}$ 中有一个为 $-1$，用 $sum$ 异或另一个元素即可获得为 $-1$ 元素的值。 1. $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)$，即可通过本题。 # 代码 ```cpp #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; } ```