Hướng dẫn giải của Cặp số tương thích (Đề THCS Phú Thọ 2023-2024)
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 cặp ~(i, j)~ với ~0 < j - i \le k~ và ~a_i = a_j~.
Sub 1: Thử các cặp trong khoảng k — ~O(n \cdot k)~, dùng khi ~n \le 5000~
Với mỗi ~i~, duyệt ~j~ từ ~i + 1~ đến ~i + k~ và đếm các cặp có giá trị bằng nhau. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 2: Hai con trỏ theo từng giá trị — ~O(n \log n)~
Gom vị trí xuất hiện của từng giá trị. Với mỗi vị trí ~j~, dùng con trỏ ~l~ để đưa về vị trí xa nhất còn trong khoảng ~k~, khi đó có ~j - l~ cặp. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~n \le 5000~ 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; // a[0..n-1]
// Sub 1: thu tung cap (i, j) voi 0 < j - i <= k — O(n * k), dung khi n <= 5000
void sub1() {
long long ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n && j - i <= K; j++)
if (a[i] == a[j]) ans++;
cout << ans << "\n";
}
// Sub 2: gom vi tri cua tung gia tri, moi gia tri dung hai con tro de dem cap co khoang cach <= k
void sub2() {
map<long long, vector<int>> pos;
for (int i = 0; i < n; i++) pos[a[i]].push_back(i);
long long ans = 0;
for (auto &e : pos) {
vector<int> &p = e.second; // vi tri tang dan
int l = 0;
for (int j = 0; j < (int)p.size(); j++) {
while (p[j] - p[l] > K) l++; // dua l ve vi tri xa nhat con trong khoang k
ans += j - l; // cac vi tri p[l..j-1] la cap voi p[j]
}
}
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 <= 5000) sub1();
else sub2();
return 0;
}
Bình luận