P8241 题解

· · 题解

题目传送门

这道题显然是让我们找规律。

不妨先模拟一下：

k 屏幕的输出 \texttt A 的个数 \texttt B 的个数
1 B 0 1
2 BA 1 1
3 BAB 1 2
4 BABBA 2 3
5 BABBABAB 3 5
6 BABBABABBABBA 5 8

不难看出，每个字母的个数是呈斐波那契数列上升的。

下面给出本蒟蒻的证明过程：

首先设当 k = i 时 \texttt A 的个数为 a_i，\texttt B 的个数为 b_i。

根据题目“每当他按一次按钮，屏幕上的字母 \texttt B 变为 \texttt{BA}，而字母 \texttt A 变为 \texttt{B}”可知：a_i = b_{i - 1}，b_i = b_{i - 1} + a_{i - 1} = b_{i - 1} + b_{i - 2}，则 a_i = b_{i - 2} + b_{i - 3} = a_{i - 1} + a_{i - 2}，即可得到上述结论。

所以 a_i = fib_{i - 1}，b_i = fib_{i}。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int k, a[50];
    cin>>k;
    a[0] = 0;
    a[1] = 1;
    a[2] = 1;
    for (int i = 3;i <= k;i++)
        a[i] = a[i - 1] + a[i - 2];
    cout<<a[k - 1]<<" "<<a[k];
}

都看到这了，点个赞再走？