d703 - SOS ~~~

🔗 前往 ZeroJudge 原題

題目描述

題目要求輸出 n 個 'S' (短音) 和 m 個 'L' (長音) 的所有排列組合。

解題思路

這題的核心是產生所有可能的字串排列。程式碼首先根據輸入的 n 和 m 建立一個包含 n 個 'S' 和 m 個 'L' 的字串 ans。然後，使用 prev_permutation 函式產生所有可能的排列，並逐一輸出。prev_permutation 函式會將字串排列成字典序中前一個排列，因此需要使用 do...while 迴圈來確保輸出所有排列，包括原始排列。

複雜度分析

• 時間複雜度: O((n+m)!)，因為需要產生所有 (n+m) 個字符的排列。
• 空間複雜度: O(n+m)，主要用於儲存字串 ans。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int s,l;
	while(cin >> s >> l){
		string ans;
		while(s--)
			ans+='S';
		while(l--)
			ans+='L';
		do{
			cout << ans << "\n";
		}while(prev_permutation(ans.begin(),ans.end()));
		cout << "\n";
	}
}