Hướng dẫn giải của [VT Thiếu nhi] BÀI 09: GIAIMATHU
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho xâu mã hoá gồm các chữ cái thường và các chữ số '1', '2'. Mỗi từ được đặt sau một chữ số: '1' nghĩa là giữ nguyên, '2' nghĩa là viết ngược lại. Đưa ra các từ đã giải mã, cách nhau một khoảng trắng.
Sub 1: Vét cạn — ~O(n^2)~
Lặp lại: lấy từ đầu tiên của xâu (chữ số đánh dấu và các chữ cái đứng sau nó đến chữ số tiếp theo), đảo ngược nếu cần, in ra, rồi cắt bỏ phần đó khỏi xâu. Mỗi lần cắt xâu tốn thời gian nên chậm với xâu dài. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("GIAIMATHU.INP", "r", stdin);
freopen("GIAIMATHU.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
// Vét cạn: lặp lại, mỗi lần tìm từ đầu tiên (chữ số đứng trước + các chữ cái sau nó),
// in ra rồi xoá khỏi xâu
bool first = true;
while (!s.empty()) {
// s[0] là chữ số đánh dấu, tìm chữ số tiếp theo để biết kết thúc từ
int q = 1;
while (q < (int)s.size() && !isdigit(s[q])) q++;
string w = s.substr(1, q - 1);
if (s[0] == '2') reverse(w.begin(), w.end());
if (!first) cout << ' ';
cout << w;
first = false;
s = s.substr(q);
}
cout << '\n';
return 0;
}
Sub 2: Duyệt một lượt — ~O(n)~
Duyệt từng ký tự. Gặp chữ số thì kết thúc từ trước (đảo ngược nếu chữ số của nó là '2') và bắt đầu từ mới với chế độ mới; gặp chữ cái thì nối vào từ hiện tại. Lưu ý kết thúc từ cuối cùng sau vòng lặp. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("GIAIMATHU.INP", "r", stdin);
freopen("GIAIMATHU.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
// Duyệt một lượt: gặp chữ số thì bắt đầu từ mới với chế độ đó,
// gặp chữ cái thì nối vào từ hiện tại
vector<string> words;
char mode = '1';
string cur;
bool started = false;
for (char c : s) {
if (isdigit(c)) {
if (started) {
// Kết thúc từ trước: nếu chế độ là '2' thì viết ngược lại
if (mode == '2') reverse(cur.begin(), cur.end());
words.push_back(cur);
}
cur.clear();
mode = c;
started = true;
} else {
cur += c;
}
}
if (started) {
if (mode == '2') reverse(cur.begin(), cur.end());
words.push_back(cur);
}
for (size_t i = 0; i < words.size(); i++) {
if (i) cout << ' ';
cout << words[i];
}
cout << '\n';
return 0;
}
Bình luận