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

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...