Hướng dẫn giải của Tương đồng
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: đếm số cặp bức tranh có hiệu mã màu không lớn hơn ~X~.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Duyệt mọi cặp ~(i, j)~ và kiểm tra ~|a_i - a_j| \le X~.
Nếu chỉ nộp sub này: đúng 9/17 test.
Sub 2: Đếm theo giá trị màu — ~O(n + A)~ với ~A = 10^6~
Đếm số bức tranh theo từng màu ~cnt[v]~ rồi lấy tổng tiền tố ~S[v]~. Cặp cùng màu có ~cntv/2~ cách. Cặp khác màu với hiệu từ 1 đến ~X~ có ~cnt[v] \cdot (S[v+X] - S[v])~ cách. Kết quả có thể rất lớn nên dùng số nguyên 64 bit.
Nếu chỉ nộp sub này: đúng 17/17 test.
Chương trình hoàn chỉnh
Với ~n > 1000~ chương trình dùng sub 2. Sub 2 không phụ thuộc ~n~ nên đủ nhanh cho ~n \le 10^7~ nếu đọc dữ liệu nhanh (dùng fread thay cho cin). 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 X;
vector<int> a; // a[0..n-1]: mã màu các bức tranh
// Sub 1: vét cạn O(n^2) — dùng khi n <= 1000
void sub1() {
long long ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (llabs((long long)a[i] - a[j]) <= X) ans++;
cout << ans << "\n";
}
// Sub 2: đếm theo giá trị màu O(n + maxA) — lời giải đầy đủ
// cnt[v] = số bức tranh có màu v; S[v] = cnt[0] + ... + cnt[v].
// Cặp (u, v) với u < v, v - u <= X: cnt[u] * (số tranh có màu trong (u, u+X]).
void sub2() {
const int M = 1000000;
vector<long long> cnt(M + 1, 0), S(M + 1, 0);
for (int x : a) cnt[x]++;
for (int v = 0; v <= M; v++) S[v] = (v ? S[v - 1] : 0) + cnt[v];
long long ans = 0;
for (int v = 0; v <= M; v++) {
if (cnt[v] == 0) continue;
ans += cnt[v] * (cnt[v] - 1) / 2; // cặp cùng màu
long long hi = min<long long>(M, (long long)v + X);
ans += cnt[v] * (S[hi] - S[v]); // cặp khác màu, hiệu <= X
}
cout << ans << "\n";
}
int main() {
freopen("Tuongdong.inp", "r", stdin);
freopen("Tuongdong.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
// đọc nhanh bằng fread theo từng khối vì n có thể tới 10^7
static char buf[1 << 16];
size_t len = 0, pos = 0;
auto gc = [&]() -> int {
if (pos == len) { len = fread(buf, 1, sizeof(buf), stdin); pos = 0; if (len == 0) return -1; }
return buf[pos++];
};
auto readInt = [&]() -> long long {
int c = gc();
while (c != -1 && (c < '0' || c > '9')) c = gc();
long long x = 0;
while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
return x;
};
n = readInt(); X = readInt();
a.resize(n);
for (int i = 0; i < n; i++) a[i] = readInt();
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận