企业官网建设流程全解析

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;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容