d671 - 11716 - Digital Fortress

🔗 前往 ZeroJudge 原題

題目描述

題目給定一個字串，要求判斷字串長度是否為完全平方數。如果是，則將字串重新排列成一個正方形矩陣，並按照行優先的方式讀取矩陣中的字元，輸出重新排列後的字串。如果字串長度不是完全平方數，則輸出 "INVALID"。

解題思路

首先讀取輸入的測試案例數量。對於每個測試案例，讀取密文字串。計算字串長度的平方根，如果平方根是整數，則表示字串長度是完全平方數。如果是，則計算矩陣的邊長，並按照列優先的方式將字串中的字元填入矩陣。最後，按照行優先的方式讀取矩陣中的字元，輸出重新排列後的字串。如果字串長度不是完全平方數，則輸出 "INVALID"。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是字串的長度。因為需要計算平方根和遍歷字串來填充和讀取矩陣。
• 空間複雜度: O(n^2)，因為需要創建一個 n x n 的矩陣來存儲字元。但實際上程式碼並沒有顯式地創建矩陣，而是直接使用字串索引來模擬矩陣操作，所以空間複雜度可以視為 O(1)。

程式碼

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main(){
	int a;
	cin >> a;
	string b;
	getline(cin,b);
	while(a--){
		getline(cin,b);
		float k=sqrt(b.length());
		int bb=b.length();
		if(k==sqrt(bb)){
			int g=k;
			for(int i=0;i<g;i++){
				for(int j=0;j<g;j++){
					cout << b[(i%g)+j*g];
				}
			}
		}
		else{
			cout << "INVALID";
		}
		cout << "\n";
	}
}