【C. Build Permutation】(整数理论、构造、思维)
链接
理论基础
结论：在区间[n,2n]上，至少存在一个完全平方数。结论：在区间[n,2n]上，至少存在一个完全平方数。结论：在区间[n,2n]上，至少存在一个完全平方数。
构造⌈n⌉2构造\lceil \sqrt{n}\rceil^2构造⌈n⌉2
∵n⩽⌈n⌉\because \sqrt n \leqslant \lceil \sqrt{n}\rceil∵n⩽⌈n⌉
∴n⩽⌈n⌉2\therefore n\leqslant \lceil \sqrt{n}\rceil^2∴n⩽⌈n⌉2
⌈n⌉⩽n+1\lceil \sqrt{n}\rceil \leqslant \sqrt{n} + 1⌈n⌉⩽n+1
⌈n⌉2⩽n+2n+1\lceil \sqrt{n}\rceil^2 \leqslant n+2\sqrt n+1⌈n⌉2⩽n+2n+1
何时2n⩾n+2n+1何时2n\geqslant n+2\sqrt n+1何时2n⩾n+2n+1
即n−2n−1⩾0即n-2\sqrt n-1\geqslant0即n−2n−1⩾0
(n−1)2⩾2(\sqrt n-1)^2\geqslant 2(n−1)2⩾2
当n⩾7的时候成立，而且取不到等号当n\geqslant 7的时候成立，而且取不到等号当n⩾7的时候成立，而且取不到等号
然后枚举0到6所有数0123456发现均可以找到不到2n的平方数然后枚举0到6所有数0~1~2~3~4~5~6发现均可以找到不到2n的平方数然后枚举0到6所有数0 1 2 3 4 5 6发现均可以找到不到2n的平方数
分别为−−−−−−0126543分别为------0~1~2~6~5~4~3分别为−−−−−−0 1 2 6 5 4 3
分析
这里从最后的数开始寻找，[n, 2n]，必定有一个平方数，与这个数配对的数可以是0~n的所有数，我们从后往前配对，一旦配对成功就倒置使得这些数的和均为平方数即可。面对剩余的序列如法炮制，同样是从最后一个开始找然后配对使得这些数的和均在以最后一个数为n的[n, 2n]区间内的一个数，由于倒置的和均等于头尾的和所有中间这部分倒置的和就是合法的。
实现
#include <bits/stdc++.h>
#define ll long long
#define ls (p << 1)
#define rs (p << 1 | 1)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 5;
int vis[N];
bool check(int x) {int sq = sqrt(x);return sq * sq == x;
}
void solve() {int n;cin >> n;for (int i = 0; i < n; i++) vis[i] = 0;map<int, int> mp; for (int i = n - 1; i >= 0; i--) {if (vis[i]) continue;//如果已经配对过的话int p = i;//从这个点开始往前找while (!check(p + i)) p--;//找到第一个恰好是平方的数int sum = p + i;//注意这里是ifor (int j = p; j <= i; j++) {//到i不是到n-1vis[j] = 1;mp[j] = sum - j;}}for (int i = 0; i < n; i++) {cout << mp[i] << " \n"[i == n - 1];}
}
int main(){ios::sync_with_stdio(false);cin.tie(0);int T = 1;cin >> T;while (T--) solve();return 0;
}