当前位置: 首页 > 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;模型的对话生成系…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...