P10033 题解（2023 激励计划评分 9）
FFTotoro
·
·
题解
题目链接：\color{Green}\texttt{P10033 「Cfz Round 3」Sum of Permutation}。
赛时过了 E 没过 D。挺不错的构造题。
下文令 a 为给定排列，b 为答案序列。
对于题目有个比较显然的想法：将 $b$ 除了 $a_i=1$ 的 $i$ 全都执行 $b_i\leftarrow1$。
对于 $a_i=1$ 的那个 $i$，显然放的数越小越好。有一种**有纰漏**的做法：将一个正整数 $x$ 从 $2,3,\ldots$ 开始枚举，如果 $a_{i-1}$ 或 $a_{i+1}$ 存在且等于 $x$，那么这个 $x$ 显然不合法，继续往上枚举。找到最小的满足条件的 $x$ 即可。
但是这种做法在 $a_{i-1}\in\{2,3\}\land a_{i+1}\in\{2,3\}$ 的时候 $x=4$，在序列为 $\{2,1,3,4\}$ 时会出错（此时 $a_2+a_3+a_4=2+3+1=6=4+1+1=b_2+b_3+b_4$）。于是考虑在这种情况下进行一些微调。具体地，构造 $b_{i-1}\leftarrow a_{i+1}$，$b_i=3$，$b_{i+1}\leftarrow a_{i-1}$。
但还可能出现 $a_{i-2}+a_{i-1}+a_i=b_{i-2}+b_{i-1}+b_i$ 的情况（这是与 $i-2$ 出现冲突的情况，$i+2$ 类似），此时构造 $b_{i-1}\leftarrow 1,b_i\leftarrow 4,b_{i+1}\leftarrow 2$ 即可。
放代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0; char c=getchar();
while(!isdigit(c))c=getchar();
while(isdigit(c))x=x*10+c-48,c=getchar();
return x;
} // 快读
void write(int x){
if(x>9)write(x/10);
putchar(x%10+48);
} // 快写
int main(){
int t=read();
while(t--){
int n=read();
vector<int> a(n),b(n);
for(auto &i:a)i=read();
if(n<=2){cout<<"-1\n"; continue;} // 无解
bool f=true;
for(int i=0;i<n&&f;i++)
if(b[i]=(a[i]==1)+1;a[i]==1){
while(i&&a[i-1]==b[i]||i<n-1&&a[i+1]==b[i])b[i]++;
if(b[i]>n||a[i-1]+a[i]+a[i+1]==b[i-1]+b[i]+1)f=false;
}
if(!f){ // 第一种构造方式有问题，使用第二种
fill(b.begin(),b.end(),1);
for(int i=0;i<n;i++)
if(a[i]==1){
b[i-1]=a[i+1],b[i]=3,b[i+1]=a[i-1];
if(i+2<n&&a[i]+a[i+1]+a[i+2]==b[i]+b[i+1]+b[i+2])b[i+1]=1,b[i]=4,b[i-1]=2;
if(i>=2&&a[i]+a[i-1]+a[i-2]==b[i]+b[i-1]+b[i-2])b[i-1]=1,b[i]=4,b[i+1]=2;
} // 进行微调
}
for(int i:b)write(i),putchar(32);
putchar(10); // 汇报答案
}
return 0;
}
```