P8241Solution

题意简述

屏幕初始为 $\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)$。

参考代码

221 Bcpp

#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;
}