当前位置: 首页 > news >正文

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应用层详细设计方案&#xff08;基于Qt Widgets&#xff09; 版本&#xff1a;1.0 日期&#xff1a;2023年10月 一、系统概述 1.1 功能需求 开机流程&#xff1a;长按电源键启动&#xff0c;全屏显示商标动画&#xff08;快闪3~4次&#xff09;。主界面&…...

SpringBoot源码解析(十一):准备应用上下文

SpringBoot源码系列文章 SpringBoot源码解析(一)&#xff1a;SpringApplication构造方法 SpringBoot源码解析(二)&#xff1a;引导上下文DefaultBootstrapContext SpringBoot源码解析(三)&#xff1a;启动开始阶段 SpringBoot源码解析(四)&#xff1a;解析应用参数args Sp…...

CSS 使用white-space属性换行

一、white-space属性的常见值 * 原本格式&#xff1a; 1、white-space:normal 默认值&#xff0c;空格和换行符会被忽略过滤掉&#xff1b;宽度不够时文本会自动换行 * 宽度足够时&#xff0c;normal 处理后的格式 * 宽度不够时&#xff0c; normal 处理后的格式 2、white-spa…...

论文笔记(七十二)Reward Centering(四)

Reward Centering&#xff08;四&#xff09; 文章概括摘要附录A 伪代码 文章概括 引用&#xff1a; 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格式文件

点击图像的右上角&#xff0c;点击第一个保存按钮键。...

官方文档学习TArray容器

一.TArray中的元素相等 1.重载一下 元素中的 运算符&#xff0c;有时需要重载排序。接下来&#xff0c;我们将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&#xff08;Tiny Encryption Algorithm&#xff09;算法是一种分组加密算法&#xff0c;由剑桥大学计算机实验室的‌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看到我们的环境创建成功了&#xff0c;但是发现他是创建在我们默认的C盘的…...

详解 为什么 tcp 会出现 粘包 拆包 问题

TCP 会出现 粘包 和 拆包 问题&#xff0c;主要是因为 TCP 是 面向字节流 的协议&#xff0c;它不关心应用层发送的数据是否有边界&#xff0c;也不会自动分割或合并数据包。由于 TCP 的流控制和传输机制&#xff0c;数据可能在传输过程中被拆分成多个小的 TCP 包&#xff0c;或…...

Linus的基本命令

以下是一些常见的 Linux 命令&#xff1a; 一、文件和目录操作&#xff1a; - ls&#xff1a;列出目录中的文件和子目录&#xff0c;常用参数有 -a &#xff08;显示所有文件&#xff0c;包括隐藏文件&#xff09;、 -l &#xff08;显示详细信息&#xff09;、 -h &#xff0…...

【Linux】缓冲区和文件系统

个人主页~ 缓冲区和文件系统 一、FILE结构1、fd2、缓冲区&#xff08;一&#xff09;有换行有return全部打印&#xff08;二&#xff09;无换行无return的C接口打印&#xff08;三&#xff09;无换行无return的系统调用接口打印&#xff08;四&#xff09;有换行无return的C接口…...

函数式编程:概念、特性与应用

1. 函数式编程简介 函数式编程&#xff0c;从名称上看就与函数紧密相关。它是一种我们常常使用却可能并未意识到的编程范式&#xff0c;关注代码的结构组织&#xff0c;强调一个纯粹但在实际中有些理想化的不可变世界&#xff0c;涉及数学、方程和副作用等概念&#xff0c;甚至…...

git中的merge和rebase的区别

在 Git 中&#xff0c;git merge 和 git rebase 都是用于整合分支变更的核心命令&#xff0c;但它们的实现方式和结果有本质区别。以下是两者的详细对比&#xff1a; 一、核心区别 特性git mergegit rebase历史记录保留分支拓扑&#xff0c;生成新的合并提交线性化历史&#x…...

【目标检测】目标检测中的数据增强终极指南:从原理到实战,用Python解锁模型性能提升密码(附YOLOv5实战代码)

&#x1f9d1; 博主简介&#xff1a;曾任某智慧城市类企业算法总监&#xff0c;目前在美国市场的物流公司从事高级算法工程师一职&#xff0c;深耕人工智能领域&#xff0c;精通python数据挖掘、可视化、机器学习等&#xff0c;发表过AI相关的专利并多次在AI类比赛中获奖。CSDN…...

uniapp在app下使用mqtt协议!!!支持vue3

什么&#xff1f;打包空白&#xff1f;分享一下我的解决方法&#xff01; 第一步 找大师算过了&#xff0c;装4.1版本运气好&#xff01; 所以根目录执行命令… npm install mqtt4.1.0第二步 自己封装一个mqtt文件方便后期开坛做法&#xff01; // utils/mqtt.js import mqt…...

VMware虚拟机17.5.2版本下载与安装(详细图文教程包含安装包)

文章目录 前言一、vmware虚拟机下载二、vmware虚拟机安装教程三、vmware虚拟机许可证 前言 VMware Workstation Pro 17 功能强大&#xff0c;广受青睐。本教程将带你一步步完成它的安装&#xff0c;简单易上手&#xff0c;助你快速搭建使用环境。 一、vmware虚拟机下载 VMwar…...

如何加固织梦CMS安全,防webshell、防篡改、防劫持,提升DedeCMS漏洞防护能力

织梦系统&#xff08;DedeCMS&#xff09;是一款非常知名的CMS系统&#xff0c;因其功能强大、结构科学合理&#xff0c;深受广大用户喜欢。 虽然织梦CMS&#xff08;DedeCMS&#xff09;非常优秀&#xff0c;但是为了保障网站安全&#xff0c;我们还是需要做一些必要的防护措…...

STM32的HAL库开发---ADC采集内部温度传感器

一、STM32内部温度传感器简介 二、温度计算方法 F1系列&#xff1a; 从数据手册中可以找到V25和Avg_Slope F4、F7、H7系列只是标准值不同&#xff0c;自行查阅手册 三、实验简要 1、功能描述 通过ADC1通道16采集芯片内部温度传感器的电压&#xff0c;将电压值换算成温度后&…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容

目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法&#xff0c;当前调用一个医疗行业的AI识别算法后返回…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

Ubuntu系统多网卡多相机IP设置方法

目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机&#xff0c;交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息&#xff0c;系统版本&#xff1a;Ubuntu22.04.5 LTS&#xff1b;内核版本…...

ZYNQ学习记录FPGA(一)ZYNQ简介

一、知识准备 1.一些术语,缩写和概念&#xff1a; 1&#xff09;ZYNQ全称&#xff1a;ZYNQ7000 All Pgrammable SoC 2&#xff09;SoC:system on chips(片上系统)&#xff0c;对比集成电路的SoB&#xff08;system on board&#xff09; 3&#xff09;ARM&#xff1a;处理器…...