CF1713C Build Permutation 题解

· · 题解

题目链接

可能更好的食用体验

思路

看起来或许无从下手，所以我们从小的 n 开始枚举找规律。

\begin{aligned} &n=1:\quad 0\\ &n=2:\quad 1\,0\\ &n=3:\quad 1\,0\,2\\ &n=4:\quad 0\,3\,2\,1\\ &n=5:\quad 4\,3\,2\,1\,0\\ &n=6:\quad 0\,3\,2\,1\,5\,4\\ &n=7:\quad 1\,0\,2\,6\,5\,4\,3\\ &n=8:\quad 1\,0\,7\,6\,5\,4\,3\,2\\ &n=9:\quad 0\,8\,7\,6\,5\,4\,3\,2\,1\\ \end{aligned}

我们设 \text{sub}(i)+i 是一个完全平方数。 不难想到，一个 0 至 n 的一个优秀排列中，从 \text{sub}(n) 位开始，是一个以 n 位首项的降序序列。因为如果 n + \text{sub}(n) 位完全平方数，那么 (n-1)+(\text{sub}(n)+1) 也为相同的完全平方数，以此类推。

那 \text{sub}(n) 前面的怎么解决呢？因为第 \text{sub}(n) 位前面的一定是一个 0 至 \text{sub}(n)-1 的一个优秀排列，我们只需要去递归解决这个子问题就可以了。

Code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+15;
int T;
int n;
int a[N];
int sub(int a){
    int i;
    for(i=0;i*i<a;i++);
    return i*i-a;
}
void dfs(int n){
    if(n==0)return (void)(a[0]=0);
    int t=sub(n);
    dfs(t-1);
    for(int i=t,j=n;i<=n;i++,j--)a[i]=j;
}
void solve(){
    cin>>n;
    dfs(--n);
    for(int i=0;i<=n;i++)cout<<a[i]<<' ';
    puts("");
}
signed main(){
    cin>>T;
    while(T--)solve();
    return 0;
}