自动搬运

查看原文

来自洛谷，原作者为

	Lsrh666 Ciallo～(∠・ω< )⌒★

搬运于2025-08-24 22:29:25，当前版本为作者最后更新于2024-11-11 11:28:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

${\color{Violet} \mathfrak{description} }$

构造一棵树使得：

• 要求1：树的大小 $n$ 尽量小。
• 要求2：相邻点的编号不同。
• 要求3：树的最大编号不能小于 $k$。

同时给定 $x$，要求 $n\leq x$。

${\color{Violet} \mathfrak{solution} }$

为了方便维护，不妨设最大值 $x$ 为根。
发现此时，$x$ 必定有 $1 \sim x-1$ 的儿子。
证明是显然的，假如没有这些儿子中的任意一个 $x_{sp}$，将 $x$ 换成 $x_{sp}$，可以使树的最大值变成 $x-1$。
接下来考虑换值，考虑到要求2，将根的儿子 $i$ 换成 $i+1$，同时将 $x$ 换成 $i$。
但是一个 $i$ 是不够的，我们需要 $r-i+1$ 个这样的儿子。
但是，这样需要的操作次数太多，导致挂到55pts。
需要优化！
考虑到 $i=x-1$ 的时候，我们用 $x-1$ 替换掉了 $x$。
这样，$x$ 就又重复出现了。
考虑用 $x-2$ 换掉 $x-1$，用 $x-3$ 换掉 $x-2$
但是 $x-3$ 可以用 $x-1$ 换掉，这样就循环起来了。
这样能实现减少总节点数的功能。

${\color{Violet} \mathfrak{code} }$

#include <bits/stdc++.h>
#define int long long
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define epr(i,j) for(int i=head[j];i;i=nxt[i])
using namespace std;

const int MAXN=1e6+10;
int head[MAXN],to[MAXN<<1],nxt[MAXN<<1];
int cnt=0,tot=0;

inline void add(int x,int y){
    to[++cnt]=y,nxt[cnt]=head[x];
    head[x]=cnt;
}
inline int sol(int p,int cur){
    int res=++tot;
    if(p==1) return tot;
    if(res==1) add(res,sol(p-1,1));
    per(i,p-1-(res==1),1) rep(j,1,p-i+1+cur) add(res,sol(i,0));
    return res;
}

signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    int k,x; cin>>k>>x;
    sol(k,0);
    cout<<tot<<'\n';
    rep(i,1,tot) epr(j,i) 
    cout<<i<<' '<<to[j]<<'\n';
	return 0;
}