题解：CF2031C Penchick and BBQ Buns
chenxi2009
2024-11-18 09:10:35
思路
$n$ 为奇数时，因为有一个数要出现三次，这三次两两之间的距离差显然得是一对勾股数的平方，最小时为 $3^2+4^2=5^2$。对应地需要在答案序列 $a$ 中 $a_1,a_{10},a_{26}$ 放上相同的数，因为没有更小的勾股数所以 $n<26$ 无解。\
$n\ge27$ 时，在 $a_{23},a_{27}$ 放上相同的数，被隔开来的空白区间长度都为偶数，用偶数的方法处理。
时间复杂度 $O(\sum n)$。
# 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int T,n,ans[200001];
int main(){
scanf("%d",&T);
while(T --){
scanf("%d",&n);
if(!(n & 1)){//偶数情况
for(int i = 1;i <= n / 2;i ++)printf("%d %d ",i,i);
printf("\n");
}
else if(n <= 26)printf("-1\n");//无解特判
else{//奇数情况
ans[1] = ans[10] = ans[26] = 1,ans[23] = ans[27] = 2;
ans[2] = ans[3] = 3,ans[4] = ans[5] = 4;
ans[6] = ans[7] = 5,ans[8] = ans[9] = 6;
ans[11] = ans[12] = 7,ans[13] = ans[14] = 8;
ans[15] = ans[16] = 9,ans[17] = ans[18] = 10;
ans[19] = ans[20] = 11,ans[21] = ans[22] = 12;
ans[24] = ans[25] = 13;
for(int i = 1;i <= 27;i ++)printf("%d ",ans[i]);
for(int i = 14;i <= n / 2;i ++)printf("%d %d ",i,i);
printf("\n");
}
}
return 0;
}
```