Hướng dẫn giải của [2627 KS3] Câu 3: Dãy Hoa
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
Yêu cầu: với mỗi test, tìm đoạn liên tiếp dài nhất có không quá ~K~ màu khác nhau; nếu bằng nhau thì lấy vị trí bắt đầu nhỏ nhất.
Sub 1: Vét cạn — ~O(n^2 \log n)~, dùng khi ~n \le 1000~
Với mỗi vị trí bắt đầu ~l~, mở rộng ~r~ và đếm số màu khác nhau bằng tập hợp. Dừng khi vượt quá ~K~ màu. Chỉ cập nhật khi độ dài tăng thực sự nên vị trí bắt đầu nhỏ nhất được giữ.
Nếu chỉ nộp sub này: đúng 13/20 test.
Sub 2: Hai con trỏ — ~O(n \log n)~
Nén mã màu về ~0 .. số màu - 1~ để dùng mảng đếm. Với mỗi ~r~, tăng ~r~ rồi co ~l~ đến khi số màu không vượt quá ~K~. Đoạn ~[l, r]~ là đoạn dài nhất kết thúc tại ~r~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Mỗi test: nếu ~n \le 1000~ gọi sub 1, còn lại gọi sub 2. 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<int> c; // mã màu đã nén về 0..(số màu - 1)
// Sub 1: thử mọi đoạn bắt đầu tại l, O(n^2 log n) — dùng khi n <= 1000
void sub1() {
int best = 0, bp = 1;
for (int l = 0; l < n; l++) {
set<int> s;
for (int r = l; r < n; r++) {
s.insert(c[r]);
if ((int)s.size() > K) break;
if (r - l + 1 > best) { best = r - l + 1; bp = l + 1; }
}
}
cout << best << " " << bp << "\n";
}
// Sub 2: hai con trỏ O(n) — lời giải đầy đủ
// Với mỗi r, giữ l nhỏ nhất sao cho đoạn [l, r] có không quá K màu.
// Chỉ cập nhật khi độ dài tăng thực sự nên vị trí bắt đầu nhỏ nhất được giữ.
void sub2() {
vector<int> cnt(n, 0);
int distinct = 0, best = 0, bp = 1, l = 0;
for (int r = 0; r < n; r++) {
if (cnt[c[r]]++ == 0) distinct++;
while (distinct > K) {
if (--cnt[c[l]] == 0) distinct--;
l++;
}
if (r - l + 1 > best) { best = r - l + 1; bp = l + 1; }
}
cout << best << " " << bp << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
cin >> n >> K;
vector<int> raw(n);
for (auto &v : raw) cin >> v;
vector<int> vals = raw;
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
c.assign(n, 0);
for (int i = 0; i < n; i++)
c[i] = lower_bound(vals.begin(), vals.end(), raw[i]) - vals.begin();
if (n <= 1000) sub1();
else sub2();
}
return 0;
}
Bình luận