P1814 数的序号 题解

2023/11/20 Blog

忘了怎么发现的这道题,反正题挺水的。

解法

想要输出一棵树的结构,我们必须先知道这棵树有几个节点。

我们知道节点个数相同的一类树它们的编号是连续的。我们考虑预处理出节点个数为 $i$ 的不同的树有几种,记作 $num_i$。

每棵树肯定有一颗树根。枚举左子树的大小 $j \in [0,i-1]$,那么右子树的大小即为 $i - j - 1$,根据乘法原理,当左子树的大小为 $j$ 时节点个数为 $i$ 的不同的树有 $sum_j \times sum_{i - j - 1}$,所以 $sum_i=\sum \limits {j=0}^{n-1} sum_j\times sum{i-j-1}$。我选择了打表预处理,代码如下。

#include<bits/stdc++.h>
#define int long long
int ans[20],n;
signed main()
{
    ans[0]=1,ans[1]=1;
    for(int i=2;i<=19;i++)
    {
        for(int j=0;j<i;j++) ans[i]+=ans[j]*ans[i-j-1];
        if(ans[i]>500000000)
        {
            n=i-1;
            break;
        }
    }
    std::cout<<n<<"\n";
    for(int i=0;i<=n;i++) std::cout<<ans[i]<<",";
    return 0;
}

现在考虑两颗节点数相同的树。

一颗树的编号共同取决于其左子树的编号和右子树的编号。在左子树编号不同时,左子树编号小的树编号小。在左子树编号不同时,右子树编号小的树编号小。

考虑如何确定左、右子树的编号。这样就可以完整打印一棵树的结构了。

定义一类 $n$ 颗节点,左子树大小为 $lsiz$ 的树的初始形态如下:

       X
      / \
     X   X
      \   \
       X   X
        \   \
         X   X
          ......

此时 $id_{ori} = \sum \limits ^{n-1} {i=0} num_i$。如果想要求 $id$ 为 $id{now}$ 的树的形态,就优先改变右子树的形态 $id_{now} - id_{ori}$ 次,注意到,右子树改变了 $num_{n-lsiz-1}$ 次后就改变了一个周期。这时我们需要改变左子树的形态,在右子树改变了一个周期后左子树改变一次。

需要注意的是因为优先改变右子树,所以我们在周期中不能改变 $0$ 次右子树形态,所以需要一次特判,将 $0$ 改成 $num_{n-lsiz-1}$ 即可。

代码

#include<bits/stdc++.h>
namespace fast_IO
{
    /**
     * 快读快写
    */
};
using namespace fast_IO;
#define int long long // 害怕。
int n,num[]={1,1,2,5,14,42,132,429,1430,4862,16796,58786,208012,742900,2674440,9694845,35357670,129644790,477638700};
inline void print(int siz,int ind) // siz 表示子树大小,ind 表示子树大小为 siz 中需要打印的树的排序,第几大。
{
    if(ind==0) ind=num[siz];
    if(siz==1)
    {
        out<<'X';
        return;
    }
    int lsiz=0,cyc;
    while(ind>num[lsiz]*num[siz-lsiz-1]) ind-=num[lsiz]*num[siz-lsiz-1],lsiz++; // 确定左子树大小
    cyc=ceil(ind*1.0/num[siz-lsiz-1]);
    if(lsiz) out<<'(',print(lsiz,cyc),out<<')';
    out<<'X';
    if(siz-lsiz-1) out<<'(',print(siz-lsiz-1,ind-(cyc-1)*num[siz-lsiz-1]),out<<')';
}
signed main()
{
    int siz;
    while(1)
    {
        in>>n;
        if(n==0) break;
        siz=1;
        while(n>num[siz]) n-=num[siz],siz++;
        print(siz,n),out<<'\n';
    }
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}
对我博客最大的鼓励来自于你的评论(什么玩梗),欢迎选择 来回复, 也可以在 GitHub discussion 留言。

Search

    公告

    博主这下真摆烂了。我下辈子也不碰 Jekyll 和 MathJax 了!
    留言板,现在博主的精神状态非常好,有事烧纸。

    联系方式

    QQ: 33299235
    email: 33299235@qq.com
    Gmail: scp020.cn@gmail.com

    本人的其它个人主页

    洛谷
    CSDN

    友链

    拜谢stevehim(已退役,祝好)
    拜谢日记
    拜谢cppomstar

    views counting

    Document

    Table of Contents