P11008 『STA – R7』异或生成序列
题目描述
对于一个
1
∼
n
1 \\sim n
1∼n 的排列
{
p
n
}
\\{p_n\\}
{pn}，定义其异或生成序列为一个长度为
n
−
1
n – 1
n−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=pixorpi+1
其中
xor
\\operatorname{xor}
xor 代表按位异或运算。在 C++ 语言中由 ^ 运算符表示。
给定
n
,
{
b
n
−
1
}
n, \\{b_{n – 1}\\}
n,{bn−1}，你需要构造一个对应的排列
{
p
n
}
\\{p_n\\}
{pn}。
输入数据保证有解，如果存在多个解，输出任意一个即可。
输入格式
本题单个测试点内含有多组测试数据。
第一行一个正整数
T
T
T，代表测试数据组数。
对于每组测试数据，
-
第一行一个正整数
n
n
n。
-
第二行
n
−
1
n – 1
n−1 个非负整数，代表异或生成序列
{
b
n
−
1
}
\\{b_{n – 1}\\}
{bn−1}。
输出格式
对于每组测试数据，输出一行
n
n
n 个正整数，代表一个对应的排列
{
p
n
}
\\{p_n\\}
{pn}。如果存在多个解，输出任意一个即可。
输入输出样例 #1
输入 #1
2
4
1 2 5
6
1 7 3 2 5
输出 #1
2 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 = 1
b1=p1xorp2=2xor3=1 -
b
2
=
p
2
xor
p
3
=
3
xor
1
=
2
b_2 = p_2 \\operatorname{xor} p_3 = 3 \\operatorname{xor} 1 = 2
b2=p2xorp3=3xor1=2 -
b
3
=
p
3
xor
p
4
=
1
xor
4
=
5
b_3 = p_3 \\operatorname{xor} p_4 = 1 \\operatorname{xor} 4 = 5
b3=p3xorp4=1xor4=5
因此得到的
b
b
b 序列和输入中的相同，进而该排列符合要求。
对于第二组测试数据，
[
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^6
2≤n≤2×106； -
1
≤
T
≤
10
6
1 \\le T \\le 10^6
1≤T≤106； -
∑
n
≤
2
×
10
6
\\sum n \\le 2 \\times 10^6
∑n≤2×106; - 保证至少存在一个合法的解。
具体部分分分配如下：
| 1 |
∑ n 2 ≤ 2 × 10 6 \\sum n^2 \\le 2 \\times 10^6 ∑n2≤2×106 |
17 17 17 |
| 2 |
2 ∤ n 2 \\nmid n 2∤n |
23 23 23 |
| 3 |
4 ∣ n 4 \\mid n 4∣n |
26 26 26 |
| 4 | 无特殊限制 |
34 34 34 |
【提示】
本题输入文件较大，请使用较为快速的输入方式。
C++实现
#include<iostream>
using namespace std;
int t,n,b[(int)2e6+5],pre,ans;
bool flag[(int)2e6+5],kill[(int)2e6+5][30][2];
int main(){
cin>>t;
while(t—){
cin>>n;
for(int i=1;i<n;i++) cin>>b[i];
pre=0;
for(int i=1;i<=n;i++) flag[i]=true;
for(int i=0;i<=n;i++){
for(int j=1;j<21;j++) kill[i][j][0]=kill[i][j][1]=false;
}
for(int i=1;i<n;i++){
pre^=b[i];
if(pre<=n) flag[pre]=false;
for(int j=1;j<21;j++){
if(((n>>j–1)&1)==0) kill[(pre>>j)^(n>>j)][j][!((pre>>j–1)&1)]=true;
}
}
for(ans=1;ans<=n;ans++){
if(flag[ans]){
bool f=true;
for(int i=1;i<21;i++){
if(kill[ans>>i][i][(ans>>i–1)&1]){
f=false;
break;
}
}
if(f) break;
}
}
cout<<ans<<' ';
for(int i=1;i<n;i++){
ans^=b[i];
cout<<ans<<' ';
}
cout<<'\\n';
}
return 0;
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
