Hướng dẫn giải của Chuỗi ARN (đề Hà Nội 2021)
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
Số đoạn X không chồng lấn tối đa trong chuỗi ARN.
Sub 1: Vét cạn đệ quy, ~O(2^n)~ (n ≤ 20)
Tại mỗi vị trí chọn bỏ qua, hoặc lấy đoạn X nếu khớp. Đúng 16/25 test.
Sub 2: Tham lam, ~O(n m)~
Duyệt từ trái; khi khớp X thì đếm và nhảy qua m ký tự. Đúng 25/25 test.
Chương trình hoàn chỉnh
main: n ≤ 20 gọi sub1, còn lại gọi sub2. 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, X;
int n, m;
// Sub 1: vet can. Voi moi vi tri i, hoac bo qua, hoac (neu X khop tai i) lay doan X tai i roi nhay qua het doan do.
// Duyet moi kha nang, lay so doan nhieu nhat. Dung khi |s| <= 20.
int bestRec(int i) {
if (i + m > n) return 0;
int res = bestRec(i + 1);
if (s.compare(i, m, X) == 0) res = max(res, 1 + bestRec(i + m));
return res;
}
void sub1() {
cout << bestRec(0) << "\n";
}
// Sub 2: tham lam. Cac doan X co cung do dai m, chon doan co vi tri bat dau som nhat
// khong chong voi doan truoc: moi lan khop thi lay luon va nhay qua m ky tu.
void sub2() {
int cnt = 0;
int i = 0;
while (i + m <= n) {
if (s.compare(i, m, X) == 0) {
cnt++;
i += m;
} else {
i++;
}
}
cout << cnt << "\n";
}
int main() {
freopen("arn.inp", "r", stdin);
freopen("arn.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> s >> X;
n = s.size();
m = X.size();
if (m == 0 || m > n) {
cout << 0 << "\n";
return 0;
}
if (n <= 20) sub1();
else sub2();
return 0;
}
Bình luận