d643 - 勞動的符咒
題目描述
題目要求我們給定一個字串，將其分割成不同長度的子字串（長度為字串長度的因數），然後對這些子字串進行排序，並將排序後的子字串連接起來形成新的字串。如果新的字串與原始字串不同，則輸出這個新的字串。如果所有可能的分割和排序都產生與原始字串相同的字串，則輸出 "bomb!"。
解題思路
這個問題的解決方案是遍歷原始字串的所有因數，對於每個因數，將原始字串分割成相同長度的子字串，對這些子字串進行排序，然後將排序後的子字串連接起來。如果生成的字串與原始字串不同，則輸出該字串。使用一個 map 來儲存生成的字串，以避免重複輸出。如果沒有找到不同的字串，則輸出 "bomb!"。
複雜度分析
- 時間複雜度: O(n^2 * d)，其中 n 是字串的長度，d 是字串長度的因數個數。分割字串和排序子字串需要 O(n) 的時間，遍歷因數需要 O(d) 的時間。
- 空間複雜度: O(n)，用於儲存分割後的子字串和 map。
程式碼
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
map < string , int > ans;
int al;
bool sth;
string a;
void fd(int k){
int it=0;
string s[al/k],tmp;
for(int i=0;i<al;++i){
tmp+=a[i];
if((i+1)%k==0){
s[it]=tmp;
++it;
tmp.clear();
}
}
sort(s,s+it);
for(int i=0;i<it;++i)
tmp+=s[i];
++ans[tmp];
if(ans[tmp]==1){
cout << tmp << "\n";
sth=1;
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> a;
++ans[a];
al=a.length();
for(int i=1;i<al;++i)
if(al%i==0)
fd(i);
if(sth==0)
cout << "bomb!";
}