竞赛
考级
海螺
原神and崩铁
【算法分析】 求蜜蜂从 xxx 到 yyy 所有可能的方案数。 aia_iai 表示跨越 iii 格的方案数。 从 111 到 222 可能的路径为:1->2,a[1] = 1; 从 111 到 333 可能的路径为: 1->2->3,1->3,a[2] = 2; 从 111 到 444 可能的路径为: 1->2->3->4,1->3->4,1->2->4,a[3] = 3; 得出爬 nnn 个格子的方案数为:aia_iai = ai−1a_{i-1}ai−1 + ai−2a_{i - 2}ai−2 。 【参考代码】 【时间复杂度】 O(n)O(n)O(n) 【预计得分】 100pts100pts100pts
AC君
#include<iostream> using namespace std; int main(){ int n; cin>>n; long long a[60]; a[1]=1; a[2]=2; for(int i=3;i<=50;i++){ a[i]=a[i-2]+a[i-1]; } while(n--){ int x,y; cin>>x>>y; cout<<a[y-x]<<endl; } return 0; }
186****0568