亅新厦建设集团网站,做网站卖机器怎么弄,如何用本地视频做网站,wordpress 卸载插件一、题目
1、题目描述
给定一个层数为 n n n 的满二叉树#xff0c;每个点编号规则如下#xff1a; 具体来说#xff0c;二叉树从上往下数第 p p p 层#xff0c;从左往右编号分别为#xff1a;1,2,3,4#xff0c;…, 2p-1。
给你一条从根节点开始的路径#xff0…一、题目
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 algorithmusing 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;
}
