Hướng dẫn giải của [2526 KSCUM TT2] Câu 2: DOANTH
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
Đếm số đoạn con liên tiếp của xâu chứa đúng K chữ 'a'.
Sub 1: Vét cạn — ~O(N^2)~, dùng khi ~N \le 1000~
Với mỗi điểm bắt đầu l, duyệt r tăng dần, đếm số chữ 'a' trong ~[l..r]~ và cộng 1 khi đúng K.
Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: Tổng tiền tố — ~O(N)~
Gọi ~P_i~ là số chữ 'a' trong i ký tự đầu. Đoạn ~[l..r]~ có đúng K chữ 'a' khi ~P_r - P_{l-1} = K~. Dùng mảng tần suất của các giá trị P đã gặp để đếm: với mỗi r, cộng số lần đã gặp giá trị ~P_r - K~. Đáp án có thể lên tới khoảng ~5\cdot 10^9~ nên dùng số nguyên 64 bit.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc N, K và xâu S. Nếu N \le 1000 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, K;
string s; // xau chi gom 'a' va 'b'
// Sub 1: vet can, thu moi doan [l..r], dem so 'a' trong doan. O(n^2). Dung khi n <= 1000
void sub1() {
long long ans = 0;
for (int l = 0; l < n; l++) {
int cnt = 0;
for (int r = l; r < n; r++) {
if (s[r] == 'a') cnt++;
if (cnt == K) ans++;
}
}
cout << ans << "\n";
}
// Sub 2: dung tong tien to P[i] = so 'a' trong i ky tu dau.
// Doan [l..r] co dung K chu 'a' <=> P[r] - P[l-1] = K. Dem bang mang tan suat. O(n)
void sub2() {
vector<long long> freq(n + 1, 0);
long long ans = 0;
int P = 0;
freq[0] = 1; // P[0] = 0
for (int i = 0; i < n; i++) {
if (s[i] == 'a') P++;
if (P - K >= 0) ans += freq[P - K];
freq[P]++;
}
cout << ans << "\n";
}
int main() {
freopen("DOANTH.INP", "r", stdin);
freopen("DOANTH.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> K;
cin >> s;
n = s.size();
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận