题目

数树数【算法赛】

难度: 中等

问题描述

小蓝最近学了二叉树，他想到了一个问题。

给定一个层数为n的满二叉树，每个点编号规则如下：

具体来说，二叉树从上向下数第p层，从左往右编号分别为： 1,2,3,4...2p−1。

小蓝给你一条从根节点开始的路径，他想知道到达的节点编号是多少。

例如：路径是 right−left，那么到达的节点是1−2−31−2−3，最后到了三号点，如下图所示。

输入格式

第一行输入两个整数n,q，n表示完全二叉树的层数，q代表询问的路径数量。

接下来q行，每行一个字符串S，S只包含字符 {'L','R'}，'L'代表向左，R代表向右。

输出格式

输出q行，每行输出一个整数，代表最后到达的节点编号。

样例输入

3 6
R
L
LL
LR
RL
RR

样例输出

2
1
1
2
3
4

说明

2≤n≤20,1≤q≤103,1≤∣S∣

完全二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且节点总数是2−12k−1，则它就是满二叉树。

运行限制 语言最大运行时间最大运行内存

C++

1s

256M

1s

256M

Java

2s

256M

3s

256M

PyPy3

3s

256M

总通过次数: 1733|总提交次数: 2262|通过率: 76.6%

思路和解题方法 # ：包含输入输出流库，提供与标准输入输出设备的接口。# ：包含字符串处理函数库，提供对字符串的操作。# ：包含算法函数库，提供各种常用的算法操作。# ：包含数学函数库，提供各种常用的数学函数。int n, q, a;：声明整型变量n，q，a，用于存储输入的值和中间结果。char s[50];：声明字符数组s，用于存储输入字符串。using std;：使用std命名空间，简化对标准库的调用。int main()：主函数，程序的入口。cin >> n >> q;：从标准输入读取两个整数，分别赋值给变量n和q。for (int i = 0; i < q; i++) { ... }：循环q次，执行查询操作。cin >> s;：从标准输入读取一个字符串，赋值给字符数组s。a = 1;：将变量a初始化为1。for (int j = 0; j < (s); j++) { ... }：遍历字符串s的每个字符，进行二叉树的计算。if (s[j] == 'L') ... else ...：根据当前字符是'L'还是'R'，更新变量a的值。cout