官方题解

【算法分析】

求蜜蜂从 $x$ 到 $y$ 所有可能的方案数。
$a_i$ 表示跨越 $i$ 格的方案数。
从 $1$ 到 $2$ 可能的路径为：1->2，a[1] = 1;
从 $1$ 到 $3$ 可能的路径为: 1->2->3，1->3，a[2] = 2;
从 $1$ 到 $4$ 可能的路径为: 1->2->3->4，1->3->4，1->2->4，a[3] = 3;

得出爬 $n$ 个格子的方案数为：$a_i$ = $a_{i-1}$ + $a_{i - 2}$。

【参考代码】

#include<iostream>
using namespace std;

const int N = 60;
long long a[N];

int main() {
	int n;
	cin >> n;
	a[1] = 1; //初始条件：爬上1个格子的方案数 
	a[2] = 2; //爬上2个格子的方案数 
	for (int i = 3; i <= 50; i++) {
		a[i] = a[i - 1] + a[i - 2]; //爬i个格子的方案数 = 爬i-1个格子的方案数 + 爬i-2个格子的方案数
	}
	while (n--) {
		int x, y;
		cin >> x >> y;
		cout << a[y - x] << endl; //从x格到y格，爬上y-x个格子的方案数 
	}
	return 0;
}

【时间复杂度】

$O(n)$

【预计得分】

$100pts$