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

【蓝桥】数树数

一、题目

1、题目描述

给定一个层数为 n n n 的满二叉树,每个点编号规则如下:
在这里插入图片描述
具体来说,二叉树从上往下数第 p p p 层,从左往右编号分别为:1,2,3,4,…, 2p-1

给你一条从根节点开始的路径,想知道到达的节点编号是多少?

例如,路径是 r i g h t − l e f t right - left rightleft,那么到达的节点是 1 − 2 − 3 1-2-3 123,最后到了三号点,如下图所示:
在这里插入图片描述
输入格式:

第一行输入两个整数 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 2n20,1q103,1S<n

完全二叉树: 一个二叉树,如果每层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为 k k k,且节点总数为 2 k − 1 2^{k-1} 2k1,则它就是满二叉树。

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} 2i1 个。

在一条路径上,实际上与 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} 2pq

如果向左,则到达下一层,并且 i d id id 不变;如果向右,就是跨越了 2 p − q − 1 2^{p-q-1} 2pq1 个节点(当前节点的左树的节点全部排除), i d id id 加上 2 p − q − 1 2^{p-q-1} 2pq1

时间复杂度: 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 的满二叉树&#xff0c;每个点编号规则如下&#xff1a; 具体来说&#xff0c;二叉树从上往下数第 p p p 层&#xff0c;从左往右编号分别为&#xff1a;1,2,3,4&#xff0c;…, 2p-1。 给你一条从根节点开始的路径&#xff0…...

2、Windows下安装

目录 一.安装 1、双击下载的程序&#xff1a; 2、加载完成后&#xff0c;会进入如下界面&#xff08;选第一个Developer Default&#xff09; 3、然后点击Next 点击Execute 然后Next 4.继续next注意端口为3306 5.继续next&#xff0c;输入账户密码&#xff08;要有大小写…...

vue中transition的使用

Vue中的<transition>组件用于在元素或组件添加/移除时应用过渡动画。它能够包裹需要进行过渡效果的元素或组件&#xff0c;通过设置相应的CSS样式来实现过渡动画效果。 <transition name"过渡效果名称" before-enter"beforeEnter" enter"…...

性能测试中如何使用RunnerGo还原混合并发场景

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

KanziStudio described using object-oriented design patterns(持续更新...)

1.绑定-mvc mvc&#xff0c;model数据与view控件分离。...

线程同步的几种方式

目录 互斥锁条件变量读写锁信号量CAS-- 参考 线程同步方式有互斥锁&#xff0c;条件变量&#xff0c;信号量&#xff0c;读写锁&#xff0c;CAS锁等方式 互斥锁 互斥量 pthread_mutex_t在执行操作之前加锁&#xff0c;操作完之后解锁. 使用互斥量&#xff0c;来确保同一时刻只…...

Linux网络编程系列之服务器编程——多路复用模型

一、什么是多路复用模型 服务器的多路复用模型指的是利用操作系统提供的多路复用机制&#xff0c;同时处理多个客户端连接请求的能力。在服务器端&#xff0c;常见的多路复用技术包括select、poll和epoll等。这些技术允许服务器同时监听多个客户端连接请求&#xff0c;当有请求…...

在SQL语句里使用正则表达式,因该怎么使用

在SQL中使用正则表达式通常需要使用特定的函数或运算符&#xff0c;具体的语法可能因不同的数据库系统而有所不同。以下是使用正则表达式的一般方法&#xff0c;但请注意&#xff0c;具体语法可能会因您使用的数据库而有所不同。 一般情况下&#xff0c;您可以使用以下方法在S…...

扫码登录-测试用例设计

扫码登录测试用例...

PyTorch CUDA GPU高占用测试

0x00 问题描述 安装完成PyTorch、CUDA后&#xff0c;验证PyTorch是否能够通过CUDA高占用GPU&#xff08;占用>95%&#xff09;&#xff0c;特地使用以下代码测试。 0x01 代码设计 这个代码会持续执行神经网络的训练任务&#xff0c;每次循环都进行前向传播、反向传播和参数…...

Java|学习|abstract ,接口 Interface , Object

1.abstract 1.1 abstract abstract 是修饰符&#xff0c;表示抽象的&#xff0c;用来修饰抽象类和抽象方法。 abstract 修饰的类是抽象类&#xff0c;抽象类不能创建对象&#xff0c;主要用于被子类继承。 abstract 修饰的方法是抽象方法&#xff0c;该方法没有方法体&…...

安全的Sui Move是Web3大规模采用之路的基石

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

Python中图像相似性度量方法汇总

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

pycharm中快速对比两个.py文件

在学习一个算法的时候&#xff0c;就想着自己再敲一遍代码&#xff0c;结果最后出现了一个莫名其妙的错误&#xff0c;想跟源文件对比一下到底是在哪除了错&#xff0c;之前我都是大致定位一个一个对比&#xff0c;想起来matlab可以快速查找出两个脚本文件(.m文件)的区别&#…...

C++程序结束

在C程序任意位置结束程序需要return 0&#xff0c;如果只return的话会发生生成错误...

嵌入式学习-核心板、开发板和单片机

目录 核心板开发板单片机三者关系 核心板 核心板是一种电路板&#xff0c;它集成了微处理器、存储器和一些必要的接口电路。它通常用于嵌入式系统或物联网设备中&#xff0c;作为整个系统的核心组件。它的主要功能是将微处理器的指令和数据总线转换为各种外设的接口&#xff0…...

【pycharm】控制台报错:终端无法加载文件\venv\Scripts\activate.ps1

目录 一、在pycharm控制台输入 二、在windows的power shell &#xff08;以管理员方式打开&#xff09; 三、 在pycharm控制台输入 四、重新打开pycharm即可 前言&#xff1a;安装pycharm2022-03版本出现的终端打开报错 一、在pycharm控制台输入 get-executionpolicy …...

Python算术运算符:加减乘除 整除 取余 幂指数 小括号

运算案例 需求&#xff1a;用户手工输入梯形的上底、下底以及高&#xff0c;能直接通过Python打印出梯形的面积为多少。 做这个需求前&#xff0c;首先要知道Python的算数运算符有哪些。 2、算术运算符 所谓的算数运算符就是我们日常生活中的加减乘除等待。 运算符描述实例…...

访问者模式:对象结构的元素处理

欢迎来到设计模式系列的第十九篇文章&#xff0c;本篇将介绍访问者模式。访问者模式是一种行为型设计模式&#xff0c;它用于处理对象结构中不同类型的元素&#xff0c;而不需要修改这些元素的类。 什么是访问者模式&#xff1f; 访问者模式是一种将数据结构与数据操作分离的…...

ChatGPT快速入门

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

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战

在现代战争中&#xff0c;电磁频谱已成为继陆、海、空、天之后的 “第五维战场”&#xff0c;雷达作为电磁频谱领域的关键装备&#xff0c;其干扰与抗干扰能力的较量&#xff0c;直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器&#xff0c;凭借数字射…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

华为OD机考-机房布局

import java.util.*;public class DemoTest5 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseSystem.out.println(solve(in.nextLine()));}}priv…...

解读《网络安全法》最新修订,把握网络安全新趋势

《网络安全法》自2017年施行以来&#xff0c;在维护网络空间安全方面发挥了重要作用。但随着网络环境的日益复杂&#xff0c;网络攻击、数据泄露等事件频发&#xff0c;现行法律已难以完全适应新的风险挑战。 2025年3月28日&#xff0c;国家网信办会同相关部门起草了《网络安全…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

Unity VR/MR开发-VR开发与传统3D开发的差异

视频讲解链接&#xff1a;【XR马斯维】VR/MR开发与传统3D开发的差异【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...