简述题意

判断是否存在一个排列：

长度为 $n$ ；
$\forall i(1\le i\le n),k\in \text N^+,a_1+a_2+\cdots+a_i\ne k^2$ 。

存在则输出。

算法分析

很容易判断无解：如果

\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

不为完全平方数。

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

代码实现

CPP

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

题解：CF2071B Perfecto

文章操作

简述题意

算法分析

代码实现

相关推荐

评论

题解：CF2071B Perfecto