题解：P8241 [COCI 2013/2014 #3] RIJEČI

· · 题解

题意简述

屏幕初始为 \texttt A。每按一次按钮，每个 \texttt A 变成 \texttt B，每个 \texttt B 变成 \texttt{BA}。求按 k 次后 \texttt A、\texttt B 各有多少个。

解题思路

只需计数，不必真的拼出字符串。设按 i 次后有 a_i 个 \texttt A、b_i 个 \texttt B。\texttt A\to\texttt B 产生 1 个 \texttt B，\texttt B\to\texttt{BA} 产生 1 个 \texttt A 与 1 个 \texttt B，于是

\begin{cases} a_i=b_{i-1}\\ b_i=a_{i-1}+b_{i-1} \end{cases}

从 (a_0,b_0)=(1,0) 递推 k 步即可，数列恰是斐波那契。

时间复杂度为 O(k)。

参考代码

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int k;
    cin>>k;
    int a=1,b=0;
    while(k--)
    {
        int t=a;
        a=b;
        b=t+b;
    }
    cout<<a<<' '<<b<<'\n';
    return 0;
}