题解：P7393 「TOCO Round 1」Eternal Star

Lsrh666 · 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;
}