d353 - 幼稚數列

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算幼稚數列的第 n 項。幼稚數列的定義如下：S0 = "1"，後續每一項 Sn 是根據前一項 Sn-1 產生。產生規則是，從 Sn-1 的第一個字符開始，連續出現相同字符的次數，然後輸出這個次數和字符。例如，S1 = "11" (因為 S0 = "1" 中有一個 "1")，S2 = "21" (因為 S1 = "11" 中有兩個 "1")，S3 = "1211" (因為 S2 = "21" 中有一個 "2" 和一個 "1")，依此類推。

解題思路

這題的核心在於模擬幼稚數列的生成過程。程式碼使用一個字串陣列 ans 來儲存數列的每一項，從 S0 開始，迭代計算到 Sn。在每次迭代中，程式碼遍歷前一項 Sn-1，統計連續出現相同字符的次數，並將次數和字符添加到當前項 Sn 中。由於數列的長度會隨著項數的增加而增加，因此需要使用字串來儲存數列的每一項。

複雜度分析

• 時間複雜度: O(N * L)，其中 N 是要計算的項數，L 是數列第 N 項的長度。在最壞的情況下，L 會隨著 N 的增加而指數增長，但題目限制 n <= 30，因此 L 不會太大。
• 空間複雜度: O(L)，其中 L 是數列第 N 項的長度。程式碼使用一個字串陣列 ans 來儲存數列的每一項，因此空間複雜度取決於數列項的最大長度。

程式碼

#include <iostream>
using namespace std;
string ans[32]={"1"};
int main(){
	for(int i=0;i<31;++i){
		string b;
		char c=ans[i][0];
		int tmp=0;
		for(int j=0,al=ans[i].length();j<al;++j){
			if(c!=ans[i][j]){
				b+=tmp+48;
				b+=c;
				c=ans[i][j];
				tmp=1;
			}
			else{
				++tmp;
			}
		}
		b+=tmp+48;
		b+=c;
		ans[i+1]=b;
	}
	int n;
	while(cin >> n)
		cout << ans[n] << "\n";
}