题解：CF2071B Perfecto

Magallan_forever · 2025-03-03 19:10:13 · 题解

简要说明题意：

现在存在一个长度为 n 的全排列 p，如果 p 满足 \displaystyle{\sum_{j=1}^ip_i} 不是完全平方数对 1 \leq i \leq n 成立，那么 p 是一个完美的全排列。

给出 n，构造符合定义的全排列。

题目分析：

脑子不好不会构造，提供一个邪道做法：

注意到 \frac{n*(n+1)}{2} 好像经常不是完全平方数，那我们通过这段 Python 代码跑一下 1 \leq n \leq 500000 看看结果：

import numpy
for i in range(1,500001):
    if numpy.sqrt(i*(i+1)/2)==numpy.floor(numpy.sqrt(i*(i+1)/2)):
        print(i)

结果如下：

既然只有这么一点，那完全可以对这一点数特判：

对于 n 等于这些数的情况，答案就是 -1，否则对于 i=1,2,\dots,n，如果 i 等于这些数就先填 i+1 再填 i，否则就直接填 i。

然后就行了：

#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int T,n;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        if(n==1||n==8||n==49||n==288||n==1681||n==9800||n==57121||n==332928) printf("-1\n");
        else{
            for(int i=1;i<=n;++i)
                if(i==1||i==8||i==49||i==288||i==1681||i==9800||i==57121||i==332928) printf("%d %d ",i+1,i),++i;
                else printf("%d ",i);
            putchar('\n');
        }
    }
    return 0;
}