Hướng dẫn giải của [2526 VTT THPT KS2] Bài 3: Thay ABC [REPLABC]
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
Thao tác thay ABC bằng BCA thực chất là đẩy một chữ A sang phải qua một cặp BC liền kề. Nếu bỏ hết chữ A thì dãy B, C còn lại (gọi là ~T~) không bao giờ đổi thứ tự.
Sub 1: Vét cạn có nhớ — dùng khi ~|S| \le 30~
Thử mọi vị trí ABC, thay bằng BCA rồi đệ quy; lưu kết quả của mỗi xâu đã gặp để không tính lại. Nếu chỉ nộp sub này: đúng 11/43 test (các test lớn hơn bị lỗi bộ nhớ hoặc quá thời gian).
Sub 2: Tham lam — ~O(n)~
Mỗi chữ A đứng ở khe ~g~ (sau ~g~ ký tự của ~T~). Mỗi thao tác đưa nó từ khe ~g~ sang khe ~g+2~ và cần ~T_g T_{g+1} = BC~. Gọi ~run[g]~ là số cặp BC liên tiếp bắt đầu từ khe ~g~ (nhảy bước 2), tính từ phải sang trái. Chữ A bị chặn bởi chữ A bên phải đã dừng ở khe nào đó (một chữ A nằm giữa B và C của một cặp thì cặp đó không dùng được). Xét các chữ A từ phải sang trái: A đi tới khe xa nhất ~h \le \min(g + 2 \cdot run[g],\ bound)~ có cùng tính chẵn lẻ với ~g~, cộng ~(h-g)/2~ vào đáp án rồi đặt ~bound = h~. Chữ A bên phải đi càng xa càng tốt cho các chữ A bên trái. Nếu chỉ nộp sub này: đúng 43/43 test.
Chương trình hoàn chỉnh
Hàm main đọc file REPLABC.INP, ghi REPLABC.OUT; ~|S| \le 30~ gọi sub1 (11 test), lớn hơn gọi sub2 (32 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
string s;
// Sub 1: vét cạn có nhớ trạng thái — thử mọi cách thay ABC -> BCA, dùng khi |S| <= 30
unordered_map<string, int> memo;
int solve(const string &t) {
auto it = memo.find(t);
if (it != memo.end()) return it->second;
int best = 0;
for (size_t i = 0; i + 2 < t.size(); i++)
if (t[i] == 'A' && t[i + 1] == 'B' && t[i + 2] == 'C') {
string u = t;
u[i] = 'B'; u[i + 1] = 'C'; u[i + 2] = 'A';
best = max(best, 1 + solve(u));
}
return memo[t] = best;
}
void sub1() {
cout << solve(s) << "\n";
}
// Sub 2: tham lam — O(n)
// Bỏ các chữ A đi, dãy còn lại là T (không đổi thứ tự). Mỗi chữ A đứng ở "khe" g (sau g ký tự của T)
// và mỗi thao tác đẩy A qua một cặp "BC" liền kề của T: khe g -> g + 2.
// Xét A từ phải sang trái: A đi được đến khe xa nhất h cùng tính chẵn lẻ với g sao cho
// T[g..h) là các cặp BC liên tiếp và h không vượt quá vị trí cuối cùng của chữ A bên phải nó.
void sub2() {
string T;
vector<int> gaps; // khe của từng chữ A, từ trái sang phải
for (char ch : s) {
if (ch == 'A') gaps.push_back(T.size());
else T += ch;
}
int L = T.size();
vector<int> run(L + 3, 0); // run[g] = số cặp BC liên tiếp bắt đầu từ khe g (bước 2)
for (int g = L - 2; g >= 0; g--)
if (T[g] == 'B' && T[g + 1] == 'C') run[g] = 1 + run[g + 2];
long long ans = 0;
int bound = INT_MAX; // vị trí cuối cùng của chữ A bên phải
for (int k = (int)gaps.size() - 1; k >= 0; k--) {
int g = gaps[k];
int reach = g + 2 * run[g]; // xa nhất nếu không bị cản
int h = reach;
if (h > bound) h = bound - ((bound - g) % 2); // không vượt bound, giữ đúng chẵn lẻ
ans += (h - g) / 2;
bound = h;
}
cout << ans << "\n";
}
int main() {
freopen("REPLABC.INP", "r", stdin);
freopen("REPLABC.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> s;
if (s.size() <= 30) sub1();
else sub2();
return 0;
}
Bình luận