打卡信奥刷题（3219）用C++实现信奥题 P8279 「MCOI-08」Fill In REMATCH

rogeliu

719人浏览 · 2026-05-06 10:07:17

rogeliu · 2026-05-06 10:07:17 发布

P8279 「MCOI-08」Fill In REMATCH

题目描述

Dream 有一个长度为 $n$ （ $1≤n≤1051\le n\le 10^5$ ）的整数数组 $a1,a2,…,ana_1,a_2,\dots,a_n$ ，其中对于 $i=1,2,…,ni=1,2,\dots,n$ ，满足 $0≤ai<2600\le a_i<2^{60}$ 。

他计算了前缀异或数组 $pi=a1⊕a2⊕⋯⊕aip_i=a_1\oplus a_2\oplus\dots\oplus a_i$ 以及后缀异或数组 $si=ai⊕ai+1⊕⋯⊕ans_i=a_i\oplus a_{i+1}\oplus\dots\oplus a_n$ 。

现在 Tommy 一共将 $p$ 和 $s$ 的 $n$ 个元素换成 $- 1$ 。给定当前的 $p$ 与 $s$ 数组，请恢复任意一组可能为原数组的 $a1,a2,…,ana_1,a_2,\dots,a_n$ 。

保证存在一组合法解。

输入格式

本题有多组数据，第一行一个正整数 $t$ ，为数据组数。接下来 $t$ 组数据，其中对于每一组数据：

第一行一个正整数 $n$ （ $1≤n≤1051\le n\le 10^5$ ）。

接下来 $n$ 个整数 $p1,p2,…,pnp_1,p_2,\dots,p_n$ 。

接下来 $n$ 个整数 $s1,s2,…,sns_1,s_2,\dots,s_n$ 。

输出格式

对于每一组数据：

输出 $n$ 个非负整数 $a1,a2,…,ana_1,a_2,\dots,a_n$ ，满足以上条件。

输入输出样例 #1

输入 #1

1
4
-1 34 367 -1
3178 -1 -1 3333

输出 #1

3 33 333 3333

说明/提示

对于 $100%100\%$ 的数据， $1≤n,∑n≤1051\le n,\sum n\le 10^5$ ， $∑[pi=−1]+∑[si=−1]=n\sum [p_i=-1]+\sum [s_i=-1]=n$ ，保证有合法解。

Subtask 1（10 pts）： $n≤4n\le 4$ ， $p_i,s_i<2$ ；
Subtask 2（10 pts）： $n≤100n\le 100$ ；
Subtask 3（20 pts）： $p_i,s_i<2$ ；
Subtask 4（60 pts）：无特殊限制。

C++实现

#include<iostream>
using namespace std;
#define ll long long 
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]) << " ";
		cout << endl;
	}
	return 0;
}