P11008 『STA - R7』异或生成序列题目描述对于一个1 ∼ n 1 \sim n1∼n的排列{ p n } \{p_n\}{pn​}定义其异或生成序列为一个长度为n − 1 n - 1n−1的非负整数序列{ b n − 1 } \{b_{n - 1}\}{bn−1​}按如下方式生成b i p i xor ⁡ p i 1 b_i p_i \operatorname{xor} p_{i 1}bi​pi​xorpi1​其中xor ⁡ \operatorname{xor}xor代表按位异或运算。在 C 语言中由^运算符表示。给定n , { b n − 1 } n, \{b_{n - 1}\}n,{bn−1​}你需要构造一个对应的排列{ p n } \{p_n\}{pn​}。输入数据保证有解如果存在多个解输出任意一个即可。输入格式本题单个测试点内含有多组测试数据。第一行一个正整数T TT代表测试数据组数。对于每组测试数据第一行一个正整数n nn。第二行n − 1 n - 1n−1个非负整数代表异或生成序列{ b n − 1 } \{b_{n - 1}\}{bn−1​}。输出格式对于每组测试数据输出一行n nn个正整数代表一个对应的排列{ p n } \{p_n\}{pn​}。如果存在多个解输出任意一个即可。输入输出样例 #1输入 #12 4 1 2 5 6 1 7 3 2 5输出 #12 3 1 4 3 2 5 6 4 1说明/提示【样例解释】对于第一组测试数据我们有b 1 p 1 xor ⁡ p 2 2 xor ⁡ 3 1 b_1 p_1 \operatorname{xor} p_2 2 \operatorname{xor} 3 1b1​p1​xorp2​2xor31b 2 p 2 xor ⁡ p 3 3 xor ⁡ 1 2 b_2 p_2 \operatorname{xor} p_3 3 \operatorname{xor} 1 2b2​p2​xorp3​3xor12b 3 p 3 xor ⁡ p 4 1 xor ⁡ 4 5 b_3 p_3 \operatorname{xor} p_4 1 \operatorname{xor} 4 5b3​p3​xorp4​1xor45因此得到的b bb序列和输入中的相同进而该排列符合要求。对于第二组测试数据[ 4 , 5 , 2 , 1 , 3 , 6 ] [4,5,2,1,3,6][4,5,2,1,3,6]也是一个符合要求的排列。【数据范围】本题采用捆绑测试。对于100 % 100\%100%的数据2 ≤ n ≤ 2 × 10 6 2 \le n \le 2 \times 10^62≤n≤2×1061 ≤ T ≤ 10 6 1 \le T \le 10^61≤T≤106∑ n ≤ 2 × 10 6 \sum n \le 2 \times 10^6∑n≤2×106;保证至少存在一个合法的解。具体部分分分配如下Subtask 编号数据范围分值1∑ n 2 ≤ 2 × 10 6 \sum n^2 \le 2 \times 10^6∑n2≤2×10617 171722 ∤ n 2 \nmid n2∤n23 232334 ∣ n 4 \mid n4∣n26 26264无特殊限制34 3434【提示】本题输入文件较大请使用较为快速的输入方式。C实现#includeiostreamusingnamespacestd;intt,n,b[(int)2e65],pre,ans;boolflag[(int)2e65],kill[(int)2e65][30][2];intmain(){cint;while(t--){cinn;for(inti1;in;i)cinb[i];pre0;for(inti1;in;i)flag[i]true;for(inti0;in;i){for(intj1;j21;j)kill[i][j][0]kill[i][j][1]false;}for(inti1;in;i){pre^b[i];if(pren)flag[pre]false;for(intj1;j21;j){if(((nj-1)1)0)kill[(prej)^(nj)][j][!((prej-1)1)]true;}}for(ans1;ansn;ans){if(flag[ans]){boolftrue;for(inti1;i21;i){if(kill[ansi][i][(ansi-1)1]){ffalse;break;}}if(f)break;}}coutans ;for(inti1;in;i){ans^b[i];coutans ;}cout\n;}return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容