M02788: 二叉树（2）

http://cs101.openjudge.cn/practice/02788/

思路：

• $m$ 子树也是完全二叉树，故我们只需要关心与 $n$ 在同一层的点有哪些能取到。
• 考虑 dfs 搜索：对于 $(m,n)$，若 $m$ 子树内不存在与 $n$ 在同一层且编号 $\le n$ 的点则答案为 $0$，若 $m$ 子树内所有与 $n$ 在同一层的点的编号都 $\le n$ 则答案为 $2^{\lfloor {\log }_{2}n\rfloor -\lfloor {\log }_{2}m\rfloor }$。
• 否则，我们考虑直接对 $m$ 的两个儿子递归求解再将答案相加。
• 注意到两个儿子之中至少有一个不会再往下递归，则递归层数是 $O(\log {\displaystyle \frac{n}{m}})$ 的。
• 故时间复杂度为 $O(\sum \log {\displaystyle \frac{n}{m}})$，可以通过。

代码：

#include <stdio.h>
#include <math.h>

int solve(int m, int n, int delta){
	int l = m << delta;
	if (l > n) return 0;
	int r = l + (1 << delta) - 1;
	if (r <= n) return 1 << delta;
	return solve(m << 1, n, delta - 1) + solve(m << 1 | 1, n, delta - 1);
}

int main(){
	int m, n;
	while (true){
		scanf("%d %d", &m, &n);
		if (m == 0 && n == 0) break;
		int delta = (int)log2(n) - (int)log2(m);
		printf("%d\n", solve(m, n, delta) + ((1 << delta) - 1));
	}
	return 0;
}