大学网站建设的目标,做网站经常加班还是app,网上可以推广的地方,云南网警在线报警链接 理论基础 结论#xff1a;在区间[n,2n]上#xff0c;至少存在一个完全平方数。结论#xff1a;在区间[n,2n]上#xff0c;至少存在一个完全平方数。结论#xff1a;在区间[n,2n]上#xff0c;至少存在一个完全平方数。 构造⌈n⌉2构造\lceil \sqrt{n}\rceil^2构造⌈…链接 理论基础 结论在区间[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⌉⩽n1\lceil \sqrt{n}\rceil \leqslant \sqrt{n} 1⌈n⌉⩽n1 ⌈n⌉2⩽n2n1\lceil \sqrt{n}\rceil^2 \leqslant n2\sqrt n1⌈n⌉2⩽n2n1 何时2n⩾n2n1何时2n\geqslant n2\sqrt n1何时2n⩾n2n1 即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 pairint, 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;mapint, 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;
}
