Hướng dẫn giải của Thi thử HSG9 2026 - Ngày 4 - Con hổ
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.
Ta dễ dàng nhận xét rằng, xâu kí tự chỉ có duy nhất một cách biến đổi (việc thực hiện một phép biến đổi không ảnh hưởng đến tính khả thi của phép biến đổi khác) do ~VOI~ không trùng kí tự nào với ~TACH~. Từ đó ta đưa ra được thuật toán tham lam:
- Nếu tồn tại một cụm ~TST~, ta tăng kết quả lên 1.
- Nếu tồn tại một cụm ~TSVOI~, ta tăng kết quả lên 1 do cụm này sẽ được biến đổi thành ~TSTACH~ (có chứa cụm ~TST~).
Code mẫu (người dùng leduchuy1337):
#include <bits/stdc++.h>
using namespace std;
int main() {
freopen("TST.inp", "r", stdin);
freopen("TST.out", "w", stdout);
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
int n = s.length();
int kq = 0;
for (int i = 0; i <= n - 3; i++) {
if (s[i] == 'T' && s[i+1] == 'S' && s[i+2] == 'T') {
kq++;
}
}
for (int i = 0; i <= n - 5; i++) {
if (s[i] == 'T' && s[i+1] == 'S' && s[i+2] == 'V' && s[i+3] == 'O' && s[i+4] == 'I') {
kq++;
}
}
cout << kq;
return 0;
}
Bình luận