题解：CF2071B Perfecto

· · 题解

简述题意

判断是否存在一个排列：

存在则输出。

算法分析

很容易判断无解：如果 \dfrac{n(n+1)}{2} 为完全平方数，那么无解。

接下来判断如何输出一个解。

首先 \sum n\le10^6 告诉我们这题是 O(n) 的。

所以先构造 a_i=i。

很显然，当前不为一个正解。

我们发现，前 i 个数包含 [1,i] 的所有数。

那么前 i-1 个数的和为 \dfrac{i(i-1)}{2}。如果这个数不为完全平方数，跳过；否则，交换 i-1 和 i。

因为令 \dfrac{i(i-1)}{2}=k^2，第 i-1 个数为 z。那么新方案前 i-1 个数和为 k^2+i-z，如果 k^2+i-z=K^2，则有 K=k+1（不然和会超过），即 i-z=2k+1。

显然 k 是 \sqrt 2i 级别的，不存在 i-z\ge 2k+1，那么 k^2+i-z 不为完全平方数。

这样我们就找到了一个方案使得有解。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[114514*10],sum[114514*10];
signed main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        if((n+1)*n/2==(int)sqrt((n+1)*n/2)*(int)sqrt((n+1)*n/2)) cout<<"-1\n";
        else
        {
            for(int i=1;i<=n;i++) a[i]=i;
            for(int i=1;i<=n;i++)
            {
                sum[i]=sum[i-1]+a[i];
                if(sum[i]==(int)sqrt(sum[i])*(int)sqrt(sum[i])) swap(a[i],a[i+1]);
                sum[i]=sum[i-1]+a[i];
            }
            for(int i=1;i<=n;i++) cout<<a[i]<<' ';
            cout<<'\n';
        }
    }
    return 0;
}