j606 - 2. 造字程式

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個初始字串 $S$，以及 $Q$ 次的字串重排操作。每次操作會根據一個排列 $P$ 將字串 $S$ 的字元重新排列。最終，題目要求輸出 $R$ 行，每行包含 $Q$ 個字元，這些字元是每次操作後字串的前 $R$ 個字元。

解題思路

這題的核心在於模擬字串的重排過程。程式首先讀取初始字串 $S$ 和參數 $K, Q, R$。然後，對於每次重排操作，程式會讀取一個排列 $P$，並根據 $P$ 將字串 $S$ 的字元重新排列。每次重排後，程式會將新的字串儲存起來，以便在後續的操作中使用。最後，程式會按照題目要求的格式輸出結果。使用一個二維陣列 ans 儲存每次操作後的字串，方便後續輸出。

複雜度分析

• 時間複雜度: O(Q * K + R * Q)。其中 Q 是重排操作的次數，K 是字串的長度，R 是輸出的行數。每次重排操作需要 O(K) 的時間，總共 Q 次，所以重排操作的總時間複雜度是 O(Q * K)。輸出操作需要 O(R * Q) 的時間。
• 空間複雜度: O(R * Q)。程式使用一個二維陣列 ans 儲存每次操作後的字串，陣列的大小是 R * Q。

程式碼

#include <iostream>
using namespace std;
int k,q,r,x;
char ans[25][25];
string s,nxt;
int main(){
	cin >> k >> q >> r >> s;
	nxt=s;
	for(int i=0;i<q;++i){
		for(int j=0;j<k;++j){
			cin >> x;
			nxt[x-1]=s[j];
		}
		s=nxt;
		for(int j=0;j<r;++j)
			ans[j][i]=s[j];
	}
	for(int i=0;i<r;++i){
		for(int j=0;j<q;++j)
			cout << ans[i][j];
		cout << "\n";
	}
}