C. Build Permutation（构造/数论）

题目
参考

题意

给定一个数n，构造{0,1,2,…,n-1}的一个排列$a_0,a_1,...,a_{n-1}$，使得
对于任意的$0<=i<n$，$i+a_i$都是平方数。
一个数x为平方数，当且仅当存在一个数y，使得$x=y^2$

思路

定理：
对于任意的非负数n，区间[n,2n]至少存在一个完全平方数。
证明：
当n为0，1，2，3，4时，完全平方数分别为0，1，4，4，4。
当n>=5时，

因为 $\lceil \sqrt{n}\rceil \le \sqrt{n}+1$ ，有

$$\lceil \sqrt{n}{\rceil }^2\le n+2\sqrt{n}+1$$

又因为$n-(2\sqrt{n}+1)=n-2\sqrt{n}-1=(\sqrt{n}-1{)}^2-2>=(\sqrt{5}-1{)}^2-2>0$
，所以：
$$n<=\lceil \sqrt{n}{\rceil }^2\le n+2\sqrt{n}+1\le 2\ast n$$

所以区间[n,2n]存在平方数$\lceil \sqrt{n}{\rceil }^2$。同理，我们可以证明，区间[n,2n]存在平方数$\lceil \sqrt{2n}{\rceil }^2$

利用上述定理，我们可以构造所求序列。
对于数x，我们可以构造完全平方数$h=\lceil \sqrt{2x}{\rceil }^2$。
讲解区间上[h-x,x]上的元素构造。
接着，再用同样的方式，递归构造，处理数h-x-1。

详见代码。

官方代码

#include 
using namespace std;

const int N = 1e5 + 5;

int n, ans[N];

void recurse(int r) {
	if (r < 0) return;
	int s = sqrt(2*r); s *= s;
	int l = s - r; recurse(l - 1);
	for (; l <= r; l++, r--) {
		ans[l] = r; ans[r] = l;
	}
}

int main() {
	int tc; cin >> tc;
	while (tc--) {
		cin >> n; recurse(n - 1);
		for (int i = 0; i < n; i++)
			cout << ans[i] << ' ';
		cout << '\n';
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

最后

觉得我文章还不错的话，weixin gongzhonghao搜 对方正在debug，关注下，一起快乐刷题吧~