b764 - P32編碼
題目描述
題目要求將給定的二進制編碼字串解碼為對應的字元，並按照題目要求的格式輸出。輸入包含多組測試數據，每組數據包含多個二進制編碼字串，每個字串代表一次猜數字遊戲的過程，需要將其解碼為猜的數字和結果（幾A幾B）。
解題思路
這題的核心是將二進制字串轉換為對應的字元。題目給定了一個二進制到字元的映射表。程式碼使用一個 map 資料結構來儲存這個映射表，然後遍歷輸入的二進制字串，每次查找 map 中是否存在對應的字元。如果找到，則將字元添加到輸出字串中，並重置臨時字串。最後，按照題目要求的格式輸出結果，每 4 個字元用逗號分隔。
複雜度分析
- 時間複雜度: O(n*m)，其中 n 是測試案例的數量，m 是每個輸入字串的長度。因為需要遍歷每個輸入字串，並且在 map 中查找對應的字元。
- 空間複雜度: O(1)，因為 map 的大小是固定的（只有 12 個鍵值對），所以空間複雜度是常數級別。
程式碼
#include <iostream>
#include <map>
using namespace std;
map <string,char> ans;
int n;
string a;
int main(){
ans["00"]='A';
ans["01"]='B';
ans["100"]='0';
ans["101"]='1';
ans["1100"]='2';
ans["1101"]='3';
ans["11100"]='4';
ans["11101"]='5';
ans["111100"]='6';
ans["111101"]='7';
ans["111110"]='8';
ans["111111"]='9';
while(cin >> n){
for(int i=0;i<n;++i){
cin >> a;
int al=a.length();
string op,tmp;
for(int j=0;j<al;++j){
tmp+=a[j];
if(ans[tmp]){
op+=ans[tmp];
tmp.clear();
}
}
int ol=op.length();
for(int j=0;j<ol;++j){
if(j==4)cout << ',';
cout << op[j];
}
cout << "\n";
}
}
}