AcWing 3691:有向树形态 ← 卡特兰数 + 复旦大学考研机试题
【题目来源】
https://www.acwing.com/problem/content/3694/
【题目描述】
求 N 个相同结点能够组成的二叉树的个数。
【输入格式】
一个整数 N。
【输出格式】
输出能组成的二叉树的个数。
【数据范围】
1≤N≤20
【输入样例】
3
【输出样例】
5
【算法分析】
● 卡特兰数(Catalan number)是组合数学中一个常出现在各种计数问题中的数列。若从第 0 项开始,则卡特兰数列 h[n] 为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, …。
● 常用的卡特兰数列 h[n] 有如下 4 种等价的递推式
h[n]=h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0], (n≥2, h[0]=h[1]=1)
h[n]=h[n−1]*(4*n−2)/(n+1), (n≥2)
h[n]=C(2n,n)−C(2n,n−1), (n=0,1,2,...)
h[n]=C(2n,n)/(n+1), (n=0,1,2,...)
● 卡特兰数的第 20 项为 6564120420,大于 2×10^9,所以代码中要声明为 long long 型。
● 二叉树是有向树
(1)左子树的结点数为 0,右子树的结点数为 n-1。左子树的结点数为 1,右子树的结点数为 n-2。左子树的结点数为 n-1,右子树的结点数为 0。依此类推,可得“左子树的结点数为 k,右子树的结点数为 n-k-1”。

(2)显然,若设 h[k] 表示 k 个结点组成的二叉树的个数,那么由 n 个结点组成的二叉树的个数为 h[0]*h[n−1]+h[1]*h[n−2]+...+h[n−1]*h[0],且 h[0]=h[1]=1。显然就是上文卡特兰数的第一个通项公式。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=25;
long long c[maxn];
int n;int main() {cin>>n;c[0]=1,c[1]=1;for(int i=2; i<=n; i++)for(int j=0; j<=i-1; j++)c[i]+=c[j]*c[i-j-1];cout<<c[n];return 0;
}/*
in:
3out:
5
*/
【参考文献】
https://www.acwing.com/solution/content/104520/
https://blog.csdn.net/hnjzsyjyj/article/details/129148916
相关文章:
AcWing 3691:有向树形态 ← 卡特兰数 + 复旦大学考研机试题
【题目来源】 https://www.acwing.com/problem/content/3694/ 【题目描述】 求 N 个相同结点能够组成的二叉树的个数。 【输入格式】 一个整数 N。 【输出格式】 输出能组成的二叉树的个数。 【数据范围】 1≤N≤20 【输入样例】 3 【输出样例】 5 【算法分析】 ● 卡特…...
便携式动平衡仪Qt应用层详细设计方案(基于Qt Widgets)
便携式动平衡仪Qt应用层详细设计方案(基于Qt Widgets) 版本:1.0 日期:2023年10月 一、系统概述 1.1 功能需求 开机流程:长按电源键启动,全屏显示商标动画(快闪3~4次)。主界面&…...
SpringBoot源码解析(十一):准备应用上下文
SpringBoot源码系列文章 SpringBoot源码解析(一):SpringApplication构造方法 SpringBoot源码解析(二):引导上下文DefaultBootstrapContext SpringBoot源码解析(三):启动开始阶段 SpringBoot源码解析(四):解析应用参数args Sp…...
CSS 使用white-space属性换行
一、white-space属性的常见值 * 原本格式: 1、white-space:normal 默认值,空格和换行符会被忽略过滤掉;宽度不够时文本会自动换行 * 宽度足够时,normal 处理后的格式 * 宽度不够时, normal 处理后的格式 2、white-spa…...
论文笔记(七十二)Reward Centering(四)
Reward Centering(四) 文章概括摘要附录A 伪代码 文章概括 引用: article{naik2024reward,title{Reward Centering},author{Naik, Abhishek and Wan, Yi and Tomar, Manan and Sutton, Richard S},journal{arXiv preprint arXiv:2405.09999…...
Matlab——图像保存导出成好看的.pdf格式文件
点击图像的右上角,点击第一个保存按钮键。...
官方文档学习TArray容器
一.TArray中的元素相等 1.重载一下 元素中的 运算符,有时需要重载排序。接下来,我们将id 作为判断结构体的标识。 定义结构体 USTRUCT() struct FXGEqualStructInfo {GENERATED_USTRUCT_BODY() public:FXGEqualStructInfo(){};FXGEqualStructInfo(in…...
unxi-进程间通信
1.进程间通信实现方式 【1】同一主机 linux下通信方式: a.传统的进程间通信方式 管道 --- 进行数据传输的"管道" 无名管道 有名管道 信号 --- b.system v 进程间通信 (posix 进程间通信) 共享内存 (进程间…...
微型分组加密算法TEA、XTEA、XXTEA
微型分组加密算法TEA、XTEA、XXTEA TEA(Tiny Encryption Algorithm)算法是一种分组加密算法,由剑桥大学计算机实验室的David Wheeler和Roger Needham于1994年发明。TEA、XTEA、XXTEA算法采用64位的明文分组和128位的密钥。它使用Feistel…...
conda 基本命令
1、查询当前所有的环境 conda env list 2、创建虚拟环境 conda create -n 环境名 [pythonpython版本号] 其中[pythonpython版本号]可以不写 conda create -n test python3.12 我们输入conda env list看到我们的环境创建成功了,但是发现他是创建在我们默认的C盘的…...
详解 为什么 tcp 会出现 粘包 拆包 问题
TCP 会出现 粘包 和 拆包 问题,主要是因为 TCP 是 面向字节流 的协议,它不关心应用层发送的数据是否有边界,也不会自动分割或合并数据包。由于 TCP 的流控制和传输机制,数据可能在传输过程中被拆分成多个小的 TCP 包,或…...
Linus的基本命令
以下是一些常见的 Linux 命令: 一、文件和目录操作: - ls:列出目录中的文件和子目录,常用参数有 -a (显示所有文件,包括隐藏文件)、 -l (显示详细信息)、 -h ࿰…...
【Linux】缓冲区和文件系统
个人主页~ 缓冲区和文件系统 一、FILE结构1、fd2、缓冲区(一)有换行有return全部打印(二)无换行无return的C接口打印(三)无换行无return的系统调用接口打印(四)有换行无return的C接口…...
函数式编程:概念、特性与应用
1. 函数式编程简介 函数式编程,从名称上看就与函数紧密相关。它是一种我们常常使用却可能并未意识到的编程范式,关注代码的结构组织,强调一个纯粹但在实际中有些理想化的不可变世界,涉及数学、方程和副作用等概念,甚至…...
git中的merge和rebase的区别
在 Git 中,git merge 和 git rebase 都是用于整合分支变更的核心命令,但它们的实现方式和结果有本质区别。以下是两者的详细对比: 一、核心区别 特性git mergegit rebase历史记录保留分支拓扑,生成新的合并提交线性化历史&#x…...
【目标检测】目标检测中的数据增强终极指南:从原理到实战,用Python解锁模型性能提升密码(附YOLOv5实战代码)
🧑 博主简介:曾任某智慧城市类企业算法总监,目前在美国市场的物流公司从事高级算法工程师一职,深耕人工智能领域,精通python数据挖掘、可视化、机器学习等,发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…...
uniapp在app下使用mqtt协议!!!支持vue3
什么?打包空白?分享一下我的解决方法! 第一步 找大师算过了,装4.1版本运气好! 所以根目录执行命令… npm install mqtt4.1.0第二步 自己封装一个mqtt文件方便后期开坛做法! // utils/mqtt.js import mqt…...
VMware虚拟机17.5.2版本下载与安装(详细图文教程包含安装包)
文章目录 前言一、vmware虚拟机下载二、vmware虚拟机安装教程三、vmware虚拟机许可证 前言 VMware Workstation Pro 17 功能强大,广受青睐。本教程将带你一步步完成它的安装,简单易上手,助你快速搭建使用环境。 一、vmware虚拟机下载 VMwar…...
如何加固织梦CMS安全,防webshell、防篡改、防劫持,提升DedeCMS漏洞防护能力
织梦系统(DedeCMS)是一款非常知名的CMS系统,因其功能强大、结构科学合理,深受广大用户喜欢。 虽然织梦CMS(DedeCMS)非常优秀,但是为了保障网站安全,我们还是需要做一些必要的防护措…...
STM32的HAL库开发---ADC采集内部温度传感器
一、STM32内部温度传感器简介 二、温度计算方法 F1系列: 从数据手册中可以找到V25和Avg_Slope F4、F7、H7系列只是标准值不同,自行查阅手册 三、实验简要 1、功能描述 通过ADC1通道16采集芯片内部温度传感器的电压,将电压值换算成温度后&…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...
pam_env.so模块配置解析
在PAM(Pluggable Authentication Modules)配置中, /etc/pam.d/su 文件相关配置含义如下: 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块,负责验证用户身份&am…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
三体问题详解
从物理学角度,三体问题之所以不稳定,是因为三个天体在万有引力作用下相互作用,形成一个非线性耦合系统。我们可以从牛顿经典力学出发,列出具体的运动方程,并说明为何这个系统本质上是混沌的,无法得到一般解…...
自然语言处理——循环神经网络
自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元(GRU)长短期记忆神经网络(LSTM)…...
基于matlab策略迭代和值迭代法的动态规划
经典的基于策略迭代和值迭代法的动态规划matlab代码,实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
