题解：CF2071B Perfecto

简要说明题意：

现在存在一个长度为

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

。

然后就行了：

CPP

#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;
}

题解：CF2071B Perfecto

文章操作

简要说明题意：

题目分析：

相关推荐

评论

题解：CF2071B Perfecto