i400 - 2. 字串解碼
題目描述
題目要求解碼一個經過多層加密的字串。加密過程涉及使用多個 01 字串，每個字串對原始字串進行一次轉換。轉換包括根據 01 字串中 '1' 的數量奇偶性來翻轉字串，以及根據 01 字串的位元來決定字串的字元添加順序。目標是根據給定的加密表和加密後的字串，還原出原始字串。
解題思路
解題的核心是模擬加密的逆過程。由於加密是按照順序進行的，因此解碼也需要按照加密的相反順序進行。對於每個 01 字串，首先判斷 '1' 的數量是奇數還是偶數，如果是奇數，則需要將字串翻轉。然後，根據 01 字串的位元，將字串的字元依次添加到解碼後的字串的開頭或結尾。
複雜度分析
- 時間複雜度: O(m * n^2)，其中 m 是 01 字串的數量，n 是字串的長度。因為對於每個 01 字串，都需要遍歷字串的每個位元，並且可能需要翻轉字串。
- 空間複雜度: O(n)，因為需要儲存解碼後的字串。
程式碼
#include <iostream>
using namespace std;
int m,n;
string a[105],s;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> m >> n;
for(int i=0;i<m;++i)
cin >> a[i];
cin >> s;
for(int i=m-1;i>=0;--i){
int o=0;
string t;
for(int j=n-1;j>=0;--j){
if(a[i][j]=='1'){//54321 -> 15432
++o;
t+=s[j];
}
else{//54321 -> 43215
t=s[j]+t;
}
}
s=t;
if(o%2)
for(int j=0;j<n/2;++j)
swap(s[j],s[n/2+j+n%2]);
}
cout << s;
}