学步园

    北大的这道考研上机题的数据量比较大，暴力宽搜可能会超时，想来想去应该跟满二叉树的性质有关，即，令父节点的标号为i, 若左孩子存在，那么左孩子的标号为2*i，若右孩子存在，那么右孩子标号为2*i+1。根据这个性质我便一层一层搜，若不到最后一层，那么当前层的结点便可以全部加上，而不必挨个去计数。其实最后一层也不必挨个去计数，只要最后一层的尾结点的标号大于最左孩子的标号，那么便可以用尾结点下标剪去最左孩子的下标加1.

    题目URL：http://ac.jobdu.com/problem.php?id=1113

    我的AC代码：

#include <iostream>
#include <stdio.h>
using namespace std;

int main()
{
	int m, n, sum, left, right;
	while(scanf("%d %d", &m, &n) && (m || n))
	{
		sum = 0;
		if(m == n) sum = 1;
		else
		{
			if(m <= n)	sum = 1;
			left = 2 * m, right = 2 * m + 1;
			while(n > right)
			{
				sum += (right - left + 1);
				left *= 2, right = right * 2 + 1;
			}
			if(n >= left) sum = sum + (n - left + 1);
		}
		printf("%d\n", sum);
	}
	system("pause");
	return 0;
}