当前位置：首页 > news >正文

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

news 2026/5/7 6:19:06

P8279 「MCOI-08」Fill In REMATCH

题目描述

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

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

现在 Tommy一共将ppp和sss的nnn个元素换成−1-1−1。给定当前的ppp与sss数组，请恢复任意一组可能为原数组的a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an。

保证存在一组合法解。

输入格式

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

第一行一个正整数nnn（1≤n≤1051\le n\le 10^51≤n≤105）。

接下来nnn个整数p1,p2,…,pnp_1,p_2,\dots,p_np1,p2,…,pn。

接下来nnn个整数s1,s2,…,sns_1,s_2,\dots,s_ns1,s2,…,sn。

输出格式

对于每一组数据：

输出nnn个非负整数a1,a2,…,ana_1,a_2,\dots,a_na1,a2,…,an，满足以上条件。

输入输出样例 #1

输入 #1

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

输出 #1

3 33 333 3333

说明/提示

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

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

C++实现

#include<iostream>usingnamespacestd;#definelllonglongll p[100010];ll s[100010];llfind(intn){for(inti=0;i<=n;i++)if(p[i]!=-1&&s[i+1]!=-1)returnp[i]^s[i+1];}voidupdate(ll val,intn){for(inti=0;i<=n;i++){if(p[i]!=-1&&s[i+1]==-1)s[i+1]=val^p[i];elseif(p[i]==-1&&s[i+1]!=-1)p[i]=val^s[i+1];elseif(p[i]==-1&&s[i+1]==-1){p[i]=p[i-1];s[i+1]=val^p[i];}}}intmain(){intT;cin>>T;while(T--){intn;cin>>n;for(inti=1;i<=n;i++)cin>>p[i];for(inti=1;i<=n;i++)cin>>s[i];ll sum=find(n);//查找所有数异或的结果，记为 sumupdate(sum,n);//还原 p 数组和 s 数组for(inti=1;i<=n;i++)cout<<(p[i]^p[i-1])<<" ";cout<<endl;}return0;}