題目說明#
一個長度為 \(n\) 的字串 \(s\) 和一個長度為 \(n\) 的 01 字串 \(e\)，會產生一個加密過後的字串 \(t\)，其中加密流程為以下兩個步驟：
如果 01 字串的 1 出現次數為偶數，直接進行第二步驟，
如果出現次數為奇數則是將 字串 \(s\) 平分，兩份交換順序後再接起來，如果字串 \(s\) 的長度是奇數，中間的數不交換。讓 \(i\) 從 1 到 \(n\) 迭代，如果 \(e[i]\) = 0 就將 \(s\) 的第一個字元切掉並接到字串 \(t\) 的最後一個字元，如果是 \(e[i]\) = 1 就將 \(s\) 的最後一個字元切掉並接到字串 \(t\) 的最後一個字元。
解題過程#
題目是給加密完的字串，所以所有的步驟都要相反推回去，先做步驟 2 再做步驟 1 。
首先宣告 \(m\), \(n\) ，陣列 \(e\) 和字串 \(s\) 並輸入
int m, n;
cin >> m >> n;
vector<string> e(m);
string s;
for(int i = 0;i < m;i++){
cin >> e[i];
}
cin >> s;
從最後一個 \(e\) 往前復原加密字串
for(int i = m - 1;i >= 0;i--) {
}
for 迴圈裡面要先做步驟 2
deque <char> dq;
for(int j = n - 1;j >= 0;j--) {
if(e[i][j] == '0') dq.push_front(s[j]);
else dq.push_back(s[j]);
}
然後要把 deque 完的結果放回字串 \(s\)
s = "";
for(int j = 0;j < n;j++) {
s += dq[j];
}
接下來要做步驟 1
int odd = 0;
for(int j = 0;j < n;j++) {
if(e[i][j] == '1') odd++;
}
if(odd % 2) {
if(n % 2) {
string f = s.substr(0, n / 2);
string m = s.substr(n / 2, 1);
string l = s.substr(n / 2 + 1, n / 2);
s = l + m + f;
}
else {
string f = s.substr(0, n / 2);
string l = s.substr(n / 2,n / 2);
s = l + f;
}
}
最後在迴圈外輸出，程式就完成了!
完整的程式碼如下
#include <bits/stdc++.h>
using namespace std;
int main() {
int m, n;
cin >> m >> n;
vector <string> e(m);
string s;
for(int i = 0;i < m;i++){
cin >> e[i];
}
cin >> s;
for(int i = m - 1;i >= 0;i--) {
deque <char> dq;
for(int j = n - 1;j >= 0;j--) {
if(e[i][j] == '0') dq.push_front(s[j]);
else dq.push_back(s[j]);
}
s = "";
for(int j = 0;j < n;j++) {
s += dq[j];
}
int odd = 0;
for(int j = 0;j < n;j++) {
if(e[i][j] == '1') odd++;
}
if(odd % 2) {
if(n % 2) {
string f = s.substr(0, n / 2);
string m = s.substr(n / 2, 1);
string l = s.substr(n / 2 + 1, n / 2);
s = l + m + f;
}
else {
string f = s.substr(0, n / 2);
string l = s.substr(n / 2,n / 2);
s = l + f;
}
}
}
cout << s << endl;
return 0;
}
