2022 年上海市大学生程序设计竞赛 - 十月赛 B. Questions on Binary Tree

给定一棵n个节点的完全二叉树以及m次询问，每次询问需要计算给定节点在先序遍历的顺序。

思路就是从给定的节点不断向上跳，如果当前节点是左儿子则给答案+1，是右儿子则给答案+1+左子树的节点个数。

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
int fpow(int a, int b) {
	int ans = 1;
	for(; b; b >>= 1ll) {
		if(b & (1ll)) ans = ans * a;
		a = a * a;
	}
	return ans;
}
int calc(int n, int id) {//计算n个节点的完全二叉树中以id为根的子树的节点个数
	int ans = 0;
	int tmpl = id, tmpr = id;
	int dep1 = 0, dep2 = 0;
	while(tmpl <= n) {
		tmpl *= 2;
		dep1++;
	}
	tmpl /= 2;
	while(tmpr <= n) {
		tmpr = (tmpr * 2 + 1);
		dep2++;
	}
	tmpr /= 2;
	//如果tmpl和tmpr在同一层
	if(dep1 == dep2) {
		ans = fpow(2, dep1) - 1;
	} else {
		ans = fpow(2, dep1) - 1 - (tmpr * 2 + 1 - n);
	}
	return ans;
}
void solve() {
	int n, m;
	cin >> n >> m;
	int maxdep = 0;
	int tmp = 1;
	while(tmp <= n) {
		tmp *= 2;
		maxdep++;
	}
	int num = n - maxdep + 1;//最后一个点是这一层的第num个
	for(int i = 1; i <= m; i++) {
		//cout << i << endl;
		int x;
		cin >> x;
		int tx = x;
		int delta = 1;
		while(tx != 1) {
			if(tx & 1) {//是父亲节点的右子节点
				delta += calc(n, tx - 1) + 1;//左子节点为根的树的节点个数
			} else {
				delta++;
			}
			tx /= 2;
		}
		cout << delta << endl;
	}
}
signed main() {
	int T = 1;
	//cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}