【蓝桥】数树数
一、题目
1、题目描述
给定一个层数为 n n n 的满二叉树,每个点编号规则如下:
具体来说,二叉树从上往下数第 p p p 层,从左往右编号分别为:1,2,3,4,…, 2p-1。
给你一条从根节点开始的路径,想知道到达的节点编号是多少?
例如,路径是 r i g h t − l e f t right - left right−left,那么到达的节点是 1 − 2 − 3 1-2-3 1−2−3,最后到了三号点,如下图所示:
输入格式:
第一行输入两个整数 n n n, q q q, n n n 表示完全二叉树的层数, q q q 代表询问的路径数量。
接下来 q q q 行,每行一个字符串 S S S, S S S 只包含字符 { 'L','R'
},L
代表向左,R
代表向右。
输出格式:
输出 q q q 行,每行输出一个整数,代表最后到达节点的编号。
样例输入
3 6
R
L
LL
LR
RL
RR
样例输出:
2
1
1
2
3
4
说明:
2 ≤ n ≤ 20 , 1 ≤ q ≤ 1 0 3 , 1 ≤ ∣ S ∣ < n 2 \le n \le 20, 1 \le q \le 10^3, 1 \le |S| \lt n 2≤n≤20,1≤q≤103,1≤∣S∣<n。
完全二叉树: 一个二叉树,如果每层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 k k k,且节点总数为 2 k − 1 2^{k-1} 2k−1,则它就是满二叉树。
2、基础框架
#include <iostream>
using namespace std;int main()
{ // 请在此输入您的代码return 0;
}
3、原题链接
数树数
二、解题报告
1、思路分析
解法1:暴力解
建立起一棵 n n n 个节点的完全二叉树,然后标号,暴力走路径。
时间复杂度 O ( 2 n + ∑ ∣ S ∣ ) O(2^n + \sum|S|) O(2n+∑∣S∣)
解法2:计算
利用满二叉树的性质,第 i i i 层的节点数量是 2 i − 1 2^{i-1} 2i−1 个。
在一条路径上,实际上与 n n n 并无关系,只与最后到达的层数有关,所以只与路径的长度有关,维护当前点的编号 i d id id ,初始值为 1 1 1 ,如果路径长度是 p p p ,那么最后到达的层数就是 p p p ,当前所在的层数是 q q q ,那么当前节点的子树的叶节点总数就是 2 p − q 2^{p-q} 2p−q 。
如果向左,则到达下一层,并且 i d id id 不变;如果向右,就是跨越了 2 p − q − 1 2^{p-q-1} 2p−q−1 个节点(当前节点的左树的节点全部排除), i d id id 加上 2 p − q − 1 2^{p-q-1} 2p−q−1。
时间复杂度: O ( ∑ ∣ S ∣ ) O(\sum |S|) O(∑∣S∣) 。
2、代码详解
- 暴力解
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>using namespace std;typedef long long ll;
const int N = 2e6 + 100;
const int MOD = 998244353;int L[N], R[N], val[N];
int depVal[N];
int op = 1;void build(int u, int dpt) {val[u] = ++depVal[dpt];if (dpt == 20) {return;}L[u] = ++op;build(L[u], dpt + 1);R[u] = ++op;build(R[u], dpt + 1);
}
char s[40];void dfs(int u, char *c) {if (*c == '\0') {cout << val[u] << '\n';return;}if (*c == 'L') {dfs(L[u], c + 1);} else {dfs(R[u], c + 1);}
}void sol() {build(1, 1);int n, q;cin >> n >> q;while (q--) {cin >> s;dfs(1, s);}
}int main() {// ios::sync_with_stdio(0);// cin.tie(0);// cout.tie(0);int T = 1;// cin >> T;while (T--) {sol();}exit(0);
}
- 计算法
#include <iostream>
using namespace std;int main()
{ int n;int q;cin >> n;cin >> q;string s;while (q--) {cin >> s;int len = s.size();int ans = 1;for (int i = 0; i < len; i++) {if (s[i] == 'R') {ans += (1 << (len - i - 1)); //左树上的节点跳过} }cout << ans << endl;}return 0;
}
相关文章:

【蓝桥】数树数
一、题目 1、题目描述 给定一个层数为 n n n 的满二叉树,每个点编号规则如下: 具体来说,二叉树从上往下数第 p p p 层,从左往右编号分别为:1,2,3,4,…, 2p-1。 给你一条从根节点开始的路径࿰…...

2、Windows下安装
目录 一.安装 1、双击下载的程序: 2、加载完成后,会进入如下界面(选第一个Developer Default) 3、然后点击Next 点击Execute 然后Next 4.继续next注意端口为3306 5.继续next,输入账户密码(要有大小写…...
vue中transition的使用
Vue中的<transition>组件用于在元素或组件添加/移除时应用过渡动画。它能够包裹需要进行过渡效果的元素或组件,通过设置相应的CSS样式来实现过渡动画效果。 <transition name"过渡效果名称" before-enter"beforeEnter" enter"…...

性能测试中如何使用RunnerGo还原混合并发场景
我们在进行软件开发时经常需要进行性能测试、压力测试和负载测试。其中有一类测试场景叫做混合并发测试,需要模拟多个接口下不同数量的用户使用场景,检查同时处理多个并发任务的能力,本文将展示如何使用开源的RunnerGo还原混合并发场景。 在…...

KanziStudio described using object-oriented design patterns(持续更新...)
1.绑定-mvc mvc,model数据与view控件分离。...
线程同步的几种方式
目录 互斥锁条件变量读写锁信号量CAS-- 参考 线程同步方式有互斥锁,条件变量,信号量,读写锁,CAS锁等方式 互斥锁 互斥量 pthread_mutex_t在执行操作之前加锁,操作完之后解锁. 使用互斥量,来确保同一时刻只…...

Linux网络编程系列之服务器编程——多路复用模型
一、什么是多路复用模型 服务器的多路复用模型指的是利用操作系统提供的多路复用机制,同时处理多个客户端连接请求的能力。在服务器端,常见的多路复用技术包括select、poll和epoll等。这些技术允许服务器同时监听多个客户端连接请求,当有请求…...
在SQL语句里使用正则表达式,因该怎么使用
在SQL中使用正则表达式通常需要使用特定的函数或运算符,具体的语法可能因不同的数据库系统而有所不同。以下是使用正则表达式的一般方法,但请注意,具体语法可能会因您使用的数据库而有所不同。 一般情况下,您可以使用以下方法在S…...

扫码登录-测试用例设计
扫码登录测试用例...

PyTorch CUDA GPU高占用测试
0x00 问题描述 安装完成PyTorch、CUDA后,验证PyTorch是否能够通过CUDA高占用GPU(占用>95%),特地使用以下代码测试。 0x01 代码设计 这个代码会持续执行神经网络的训练任务,每次循环都进行前向传播、反向传播和参数…...
Java|学习|abstract ,接口 Interface , Object
1.abstract 1.1 abstract abstract 是修饰符,表示抽象的,用来修饰抽象类和抽象方法。 abstract 修饰的类是抽象类,抽象类不能创建对象,主要用于被子类继承。 abstract 修饰的方法是抽象方法,该方法没有方法体&…...

安全的Sui Move是Web3大规模采用之路的基石
没有信任,就没有Web3的大规模采用。还有其他重要障碍阻碍了首个十亿用户的到来,包括令人困惑的用户体验、复杂的身份验证模式以及不确定的监管体系,但所有障碍中,要数大多数人对区块链技术持怀疑和不信任态度最严重。 对于许多人…...

Python中图像相似性度量方法汇总
1. 引言 在当前到处充满着图像的世界里,测量和量化图像之间的相似性已经成为一项关键的任务。无论是图像检索、内容推荐还是视觉搜索,图像相似性方法在现代计算机视觉的应用中都发挥着关键的作用。 幸运的是,Python提供了大量的工具和库&am…...

pycharm中快速对比两个.py文件
在学习一个算法的时候,就想着自己再敲一遍代码,结果最后出现了一个莫名其妙的错误,想跟源文件对比一下到底是在哪除了错,之前我都是大致定位一个一个对比,想起来matlab可以快速查找出两个脚本文件(.m文件)的区别&#…...
C++程序结束
在C程序任意位置结束程序需要return 0,如果只return的话会发生生成错误...
嵌入式学习-核心板、开发板和单片机
目录 核心板开发板单片机三者关系 核心板 核心板是一种电路板,它集成了微处理器、存储器和一些必要的接口电路。它通常用于嵌入式系统或物联网设备中,作为整个系统的核心组件。它的主要功能是将微处理器的指令和数据总线转换为各种外设的接口࿰…...

【pycharm】控制台报错:终端无法加载文件\venv\Scripts\activate.ps1
目录 一、在pycharm控制台输入 二、在windows的power shell (以管理员方式打开) 三、 在pycharm控制台输入 四、重新打开pycharm即可 前言:安装pycharm2022-03版本出现的终端打开报错 一、在pycharm控制台输入 get-executionpolicy …...

Python算术运算符:加减乘除 整除 取余 幂指数 小括号
运算案例 需求:用户手工输入梯形的上底、下底以及高,能直接通过Python打印出梯形的面积为多少。 做这个需求前,首先要知道Python的算数运算符有哪些。 2、算术运算符 所谓的算数运算符就是我们日常生活中的加减乘除等待。 运算符描述实例…...
访问者模式:对象结构的元素处理
欢迎来到设计模式系列的第十九篇文章,本篇将介绍访问者模式。访问者模式是一种行为型设计模式,它用于处理对象结构中不同类型的元素,而不需要修改这些元素的类。 什么是访问者模式? 访问者模式是一种将数据结构与数据操作分离的…...

ChatGPT快速入门
ChatGPT快速入门 一、什么是ChatGPT二、ChatGPT底层逻辑2.1 实现原理2.2 IO流程 三、ChatGPT应用场景3.1 知心好友3.2 文案助理3.3 创意助理3.4 角色扮演 一、什么是ChatGPT ChatGPT指的是基于GPT(Generative Pre-trained Transformer)模型的对话生成系…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...

Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
线程与协程
1. 线程与协程 1.1. “函数调用级别”的切换、上下文切换 1. 函数调用级别的切换 “函数调用级别的切换”是指:像函数调用/返回一样轻量地完成任务切换。 举例说明: 当你在程序中写一个函数调用: funcA() 然后 funcA 执行完后返回&…...

【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...