Logo 贾永菁的博客

博客

今日打卡题222思路

2022-05-01 16:14:49 By 贾永菁

由于这题的标签是斐波那契数列。

所以我们不妨先找找规律

第一站和第二站没什么规律,所以我们从第3站找起

我们可以得出一个表

设第二站上车b人

得出下表

站 1 2 3 4 5 6 7 8 9 10

上车 a b a+b a+2b 2a+3b ······

下车 0 b b a+b a+2b ······

车上 a a 2a 2a+b 3a+2b ······

前两站车内人数 2a 3a 4a+b ······

我们来考虑一下第四行与第三行的关系

从第四站看起,你发现了什么?

    4            5

     2a+b         3a+2b 

     3a+0b             4a+1b

很明显可以发现 第四行a的个数比第三行多1,而b的个数少

我们设sum1为a的个数 sum1[i]表示第i站a的个数

sum2为b的个数,sum2[i]不用我说了。

可得出

sum1[i]=sum1[i-1]+sum1[i-2]-1(因为第四行是前两站车上人数和)

sum2[i]=sum2[i-1]+sum2[i-2]+1;(同上)

那么有了这个式子可以来推b

根据题目条件和上述公式可推出

asum1[n-1]+bsum2[n-1 ]=m;

把b挪出来得到

bsum2[n-1]=m-asum1[n-1]

化简得

b=(m-a*sum1[n-1])/sum2[n-1]

a和b都有了

答案也就出来了

评论

xushuoxin
禁止泄露AC思路!!!
Will.Pam
禁止泄露AC思路!!!
MKWMA
禁止泄露AC思路!!!! ^_^
yizexi
#70478 #222. [1998]车站 贾永菁 100 12ms 1524kb C++ 1.6kb 2022-05-01 16:14:12

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。