Hướng dẫn giải của Xem phim (KS2)
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: tìm độ dài đoạn liên tiếp dài nhất trong dãy không có phần tử nào lặp lại.
Sub 1: Vét cạn — ~O(n^2 \log n)~, dùng khi ~n \le 5000~
Với mỗi vị trí bắt đầu ~i~, đi tiếp ~j~ và dùng tập hợp để kiểm tra lặp. Gặp phần tử lặp thì dừng và cập nhật độ dài lớn nhất.
Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Hai con trỏ — ~O(n \log n)~
Giữ đoạn ~[l, r]~ không lặp. Khi thêm ~a_r~ bị trùng thì tăng ~l~ cho đến khi hết trùng. Đếm số lần xuất hiện bằng bản đồ.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Với dữ liệu lớn ~n > 5000~ chương trình dùng sub 2; dữ liệu nhỏ dùng sub 1 cho chắc. 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;
long long a[200005]; // a[1..n]: mã số các bộ phim
// Sub 1: vét cạn O(n^2 log n) — dùng khi n <= 5000
// Với mỗi vị trí bắt đầu i, đi tiếp j cho đến khi gặp bộ phim bị lặp.
void sub1() {
int best = 0;
for (int i = 1; i <= n; i++) {
set<long long> seen;
for (int j = i; j <= n; j++) {
if (seen.count(a[j])) break;
seen.insert(a[j]);
best = max(best, j - i + 1);
}
}
cout << best << "\n";
}
// Sub 2: hai con trỏ O(n log n) — lời giải đầy đủ
// Đoạn [l, r] luôn không lặp; khi thêm a[r] mà bị lặp thì co l lại.
void sub2() {
map<long long, int> cnt;
int best = 0, l = 1;
for (int r = 1; r <= n; r++) {
cnt[a[r]]++;
while (cnt[a[r]] > 1) {
cnt[a[l]]--;
l++;
}
best = max(best, r - l + 1);
}
cout << best << "\n";
}
int main() {
freopen("MOVIE.INP", "r", stdin);
freopen("MOVIE.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 5000) sub1();
else sub2();
return 0;
}
Bình luận