CF2031C 题解
include13_fAKe
2024-11-17 17:43:29
前置知识
题意
给 n 个数赋值，要求如下：
- 所有的值应该在 1 至 10^6 之间。
- 所有出现的值都至少出现两次。
- 定义距离为两个数的下标之差，每两个相同的值的距离必须为平方数。
构造一组解，或报告无解。
$T\ge 1$，$1\le n,\sum n\le 2\times10^5$。
## 思路
### $n$ 为偶数
最简单的情况。
直接 $1,1,2,2,3,3,\dots,\frac{n}{2},\frac{n}{2}$ 即可。
### $n$ 为奇数
意味着肯定有一个数会被填奇数次。
上文已提到，若填奇数次就至少为 $3$ 次。我们考虑只填 $3$ 次的情况。
因为所有的距离均为平方数，所以考虑勾股定理。
$3^2+4^2=5^2$，所以可以构造坐标 $1,10,26$ 三个数相等。剩下的按照偶数的情况处理即可。
坐标 $2\sim 9$ 按照 $n$ 为偶数的情况填即可，但坐标 $11\sim25$ 仍为奇数。下一步解决这一问题。
可以考虑将任意一个奇数坐标的数与坐标 $27$ 相同的数，只要距离为平方数就行。可选 $11$ 和 $23$。我选择的是 $23$。
然后剩下的数就可以按照 $n$ 为偶数的情况配对。做完了。
## 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int ans[30]={-1,
1,2,2,3,3,4,4,5,5,1,
6,6,7,7,8,8,9,9,10,10,
11,11,12,13,13,1,12
};
void solve(){
cin>>n;
if(n%2){
if(n<=25) puts("-1");
else{
for(int i=1;i<=27;i++){
cout<<ans[i]<<' ';
}
for(int i=28;i<=n;i++){
cout<<i/2<<' ';
}
cout<<endl;
}
return;
}
else{
for(int i=1;i<=n;i++){
cout<<(i+1)/2<<' ';
}
cout<<endl;
return;
}
}
int main(){
int T;
cin>>T;
while(T--) solve();
return 0;
}
```
为什么我们机房只有我过了这题呢？