b541 - 看到這樣的分布，網友們都驚呆了

🔗 前往 ZeroJudge 原題

題目描述

題目要求產生外觀數列的第 n 項。外觀數列的產生規則是，第 n 項描述了第 n-1 項的數字分布。例如，如果第 n-1 項是 "111221"，那麼第 n 項就是 "312211"，因為第 n-1 項包含三個 "1"，兩個 "2"，一個 "1"。

解題思路

程式碼使用一個字串陣列 ans 來儲存外觀數列的前 42 項。陣列的第一個元素 ans[0] 初始化為 "1"。然後，程式碼使用一個迴圈來產生後續的項。在每次迭代中，程式碼讀取前一個項 ans[i]，並根據其數字分布產生下一個項 ans[i+1]。

產生下一個項的過程如下：

1. 初始化一個空字串 b，用於儲存下一個項。
2. 初始化一個字元 c 為 ans[i] 的第一個字元。
3. 初始化一個計數器 tmp 為 0。
4. 遍歷 ans[i] 的每個字元。
5. 如果當前字元與 c 不同，則將 tmp 轉換為字串，並將其附加到 b，然後將 c 附加到 b，並將 c 更新為當前字元，並將 tmp 重置為 1。
6. 否則，將 tmp 增加 1。
7. 遍歷完 ans[i] 後，將 tmp 轉換為字串，並將其附加到 b，然後將 c 附加到 b。
8. 將 b 賦值給 ans[i+1]。

最後，程式碼讀取輸入的 n，並輸出 ans[n-1]。

複雜度分析

• 時間複雜度: O(N^2)，其中 N 是外觀數列的項數。因為每次產生下一項都需要遍歷前一項，而每一項的長度會隨著項數的增加而增加。
• 空間複雜度: O(N^2)，因為需要儲存所有前 N 項的外觀數列，每一項的長度會隨著項數的增加而增加。

程式碼

#include <iostream>
using namespace std;
string ans[42]={"1"};
int main(){
	for(int i=0;i<41;++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-1] << "\n";
}