博客

题意：一个长度为 n 从 0 开始的全排列数组 a，求出一种排列方式使对于所有的 i，ai + i 为完全平方数。

思路：倒着从最后一个数开始，最后一个数 i 为 n – 1，所以找到第一个大于等于 n – 1 的完全平方数，ai 就是这个完全平方数减去 n – 1，随着 i 递减，把 ai 递增就可以，当 ai 大于 n – 1 时停止，从停止的位置递归处理。

代码：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 2e5 + 10, P = 1e9 + 7, mod = 998244353;
int n;
bool check(int x){
	int k = sqrt(x);
	return k * k == x;
}
void dfs(int x){
	if(x == -1) return;
	for(int i = x; ; i++){
		if(check(i)){
			int s = i - x;
			dfs(s - 1);
			for(int j = x; j >= s; j--)
			 	cout << j << " ";
			return;
		}
	}
}
void solve(){
	cin >> n;
	dfs(n - 1);
	cout << endl;
}                
int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int tt;
	cin >> tt;
	while(tt--) {
		solve();
	}
	return 0;
}