P8279 「MCOI-08」Fill In REMATCH题目描述Dream 有一个长度为nnn1≤n≤1051\le n\le 10^51≤n≤105的整数数组a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​其中对于i1,2,…,ni1,2,\dots,ni1,2,…,n满足0≤ai2600\le a_i2^{60}0≤ai​260。他计算了前缀异或数组pia1⊕a2⊕⋯⊕aip_ia_1\oplus a_2\oplus\dots\oplus a_ipi​a1​⊕a2​⊕⋯⊕ai​以及后缀异或数组siai⊕ai1⊕⋯⊕ans_ia_i\oplus a_{i1}\oplus\dots\oplus a_nsi​ai​⊕ai1​⊕⋯⊕an​。现在 Tommy一共将ppp和sss的nnn个元素换成−1-1−1。给定当前的ppp与sss数组请恢复任意一组可能为原数组的a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​。保证存在一组合法解。输入格式本题有多组数据第一行一个正整数ttt为数据组数。接下来ttt组数据其中对于每一组数据第一行一个正整数nnn1≤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输入 #11 4 -1 34 367 -1 3178 -1 -1 3333输出 #13 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 110 ptsn≤4n\le 4n≤4pi,si2p_i,s_i2pi​,si​2Subtask 210 ptsn≤100n\le 100n≤100Subtask 320 ptspi,si2p_i,s_i2pi​,si​2Subtask 460 pts无特殊限制。C实现#includeiostreamusingnamespacestd;#definelllonglongll p[100010];ll s[100010];llfind(intn){for(inti0;in;i)if(p[i]!-1s[i1]!-1)returnp[i]^s[i1];}voidupdate(ll val,intn){for(inti0;in;i){if(p[i]!-1s[i1]-1)s[i1]val^p[i];elseif(p[i]-1s[i1]!-1)p[i]val^s[i1];elseif(p[i]-1s[i1]-1){p[i]p[i-1];s[i1]val^p[i];}}}intmain(){intT;cinT;while(T--){intn;cinn;for(inti1;in;i)cinp[i];for(inti1;in;i)cins[i];ll sumfind(n);//查找所有数异或的结果记为 sumupdate(sum,n);//还原 p 数组和 s 数组for(inti1;in;i)cout(p[i]^p[i-1]) ;coutendl;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容