石油大--2020年秋季组队训练赛第十三场----G、Insertion Order（构造）

题面：

题意：
给定 $n$， $k$ 。
需要构造一个 $1-n$ 的全排列，使得按这个顺序插入搜索二叉树，使得二叉树的树高为 $k$。
这里的树高定义为，从根节点到叶子节点经过的最多的节点个数。

题解：
先构造一棵可行的树。
可以先构造一个节点数为 $k$，树高为 $k$ 的树，我们可以让每个节点只有左儿子从而构造。
然后分层添加节点，使得树上的节点为 $n$。

然后 $dfs$ 填值即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<set>
namespace onlyzhao
{#define ui unsigned int#define ll long long#define llu unsigned ll#define ld long double#define pr make_pair#define pb push_back#define lc (cnt<<1)#define rc (cnt<<1|1)#define len(x)  (t[(x)].r-t[(x)].l+1)#define tmid ((l+r)>>1)#define fhead(x) for(int i=head[(x)];i;i=nt[i])#define max(x,y) ((x)>(y)?(x):(y))#define min(x,y) ((x)>(y)?(y):(x))#define one(n) for(int i=1;i<=(n);i++)#define rone(n) for(int i=(n);i>=1;i--)#define fone(i,x,n) for(int i=(x);i<=(n);i++)#define frone(i,n,x) for(int i=(n);i>=(x);i--)#define fonk(i,x,n,k) for(int i=(x);i<=(n);i+=(k))#define fronk(i,n,x,k) for(int i=(n);i>=(x);i-=(k))#define two(n,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)#define ftwo(i,n,j,m) for(int i=1;i<=(n);i++) for(int j=1;j<=(m);j++)#define fvc(vc) for(int i=0;i<vc.size();i++)#define frvc(vc) for(int i=vc.size()-1;i>=0;i--)#define forvc(i,vc) for(int i=0;i<vc.size();i++)#define forrvc(i,vc) for(int i=vc.size()-1;i>=0;i--)#define cls(a) memset(a,0,sizeof(a))#define cls1(a) memset(a,-1,sizeof(a))#define clsmax(a) memset(a,0x3f,sizeof(a))#define clsmin(a) memset(a,0x80,sizeof(a))#define cln(a,num) memset(a,0,sizeof(a[0])*num)#define cln1(a,num) memset(a,-1,sizeof(a[0])*num)#define clnmax(a,num) memset(a,0x3f,sizeof(a[0])*num)#define clnmin(a,num) memset(a,0x80,sizeof(a[0])*num)#define sc(x) scanf("%d",&x)#define sc2(x,y) scanf("%d%d",&x,&y)#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)#define scl(x) scanf("%lld",&x)#define scl2(x,y) scanf("%lld%lld",&x,&y)#define scl3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)#define scf(x) scanf("%lf",&x)#define scf2(x,y) scanf("%lf%lf",&x,&y)#define scf3(x,y,z) scanf("%lf%lf%lf",&x,&y,&z)#define scs(x) scanf("%s",x+1)#define scs0(x) scanf("%s",x)#define scline(x) scanf("%[^\n]%*c",x+1)#define scline0(x) scanf("%[^\n]%*c",x)#define pcc(x) putchar(x)#define pc(x) printf("%d\n",x)#define pc2(x,y) printf("%d %d\n",x,y)#define pc3(x,y,z) printf("%d %d %d\n",x,y,z)#define pck(x) printf("%d ",x)#define pcl(x) printf("%lld\n",x)#define pcl2(x,y) printf("%lld %lld\n",x,y)#define pcl3(x,y,z) printf("%lld %lld %d\n",x,y,z)#define pclk(x) printf("%lld ",x)#define pcf2(x) printf("%.2f\n",x)#define pcf6(x) printf("%.6f\n",x)#define pcf8(x) printf("%.8f\n",x)#define pcs(x) printf("%s\n",x+1)#define pcs0(x) printf("%s\n",x)#define pcline(x) printf("%d**********\n",x)#define casett int tt;sc(tt);int pp=0;while(tt--)char buffer[100001],*S,*T;inline char Get_Char(){if (S==T){T=(S=buffer)+fread(buffer,1,100001,stdin);if (S==T) return EOF;}return *S++;}inline int read(){char c;int re=0;for(c=Get_Char();c<'0'||c>'9';c=Get_Char());while(c>='0'&&c<='9') re=re*10+(c-'0'),c=Get_Char();return re;}
};
using namespace onlyzhao;
using namespace std;const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e9;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=400100;
const int maxm=100100;
const int up=100100;int si[maxn];
int son[maxn][2];
int id[maxn];
int n,k,rt=0,cnt=0;
int ans[maxn];//先构造每个点只有左儿子的树高为k的树
int dfs(int p,int kk)
{if(kk==k+1) return 0;if(p==0) p=++cnt;son[p][0]=dfs(son[p][0],kk+1);return p;
}//分层添加节点
bool bfs(int rt)
{int nowk=1;queue<int>q1,q2;int cc=k;q1.push(rt);while(true){while(q1.size()&&cc<n){int x=q1.front();q1.pop();if(!son[x][0]&&cc<n) son[x][0]=++cnt,cc++,q2.push(son[x][0]);else if(son[x][0]) q2.push(son[x][0]);if(!son[x][1]&&cc<n) son[x][1]=++cnt,cc++,q2.push(son[x][1]);else if(son[x][1]) q2.push(son[x][1]);}if(q2.size())nowk++;if(cc==n) break;swap(q1,q2);}return nowk<=k;
}void dfs(int p)
{if(!p) return ;si[p]=1;dfs(son[p][0]);dfs(son[p][1]);si[p]+=si[son[p][0]]+si[son[p][1]];
}int cp=0;
void dfs(int p,int l,int r)
{if(!p) return ;ans[++cp]=l+si[son[p][0]];dfs(son[p][0],l,l+si[son[p][0]]-1);dfs(son[p][1],l+si[son[p][0]]+1,r);
}int main(void)
{scanf("%d%d",&n,&k);rt=dfs(rt,1);if(!bfs(rt)){printf("impossible\n");return 0;}dfs(rt);dfs(rt,1,n);for(int i=1;i<=n;i++){if(i!=1) putchar(' ');printf("%d",ans[i]);}putchar('\n');return 0;
}