Hướng dẫn giải của Đếm đoạn con (KS THCS 04)
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 các đoạn con có nhiều nhất ~k~ phần tử khác nhau. Với mỗi ~r~, các ~l~ hợp lệ tạo thành một đoạn liên tiếp, nên dùng cửa sổ trượt.
Sub 1: Mở rộng từ mỗi l — ~O(n^2 \log n)~, dùng khi ~n \le 1000~
Với mỗi ~l~, mở rộng ~r~ và dừng khi số giá trị khác nhau vượt quá ~k~. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Hai con trỏ — ~O(n \log n)~
Nén giá trị, dùng cửa sổ trượt ~[l; r]~ đếm số giá trị khác nhau, mỗi ~r~ cộng ~r - l + 1~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 1000~ dùng sub 1, còn lại dùng sub 2. 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;
int n, K;
vector<long long> a;
// Sub 1: voi moi vi tri trai l, mo rong r va dem; dung khi n <= 1000
void sub1() {
long long ans = 0;
for (int l = 0; l < n; l++) {
set<long long> s;
for (int r = l; r < n; r++) {
s.insert(a[r]);
if ((int)s.size() <= K) ans++;
else break; // mo rong them chi lam so phan tu khac nhau tang
}
}
cout << ans << "\n";
}
// Sub 2: hai con tro (cua so truot) O(n log n): voi moi r, dem so l hop le
void sub2() {
vector<long long> v = a;
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
vector<int> c(n);
for (int i = 0; i < n; i++) c[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin();
vector<int> cnt(v.size(), 0);
int distinct = 0, l = 0;
long long ans = 0;
for (int r = 0; r < n; r++) {
if (cnt[c[r]]++ == 0) distinct++;
while (distinct > K) {
if (--cnt[c[l]] == 0) distinct--;
l++;
}
ans += r - l + 1;
}
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> K;
a.assign(n, 0);
for (auto &x : a) cin >> x;
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận