Hướng dẫn cho Đếm cặp đôi (HSG'20)
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Hint 1
Đề yêu cầu \((A_i, A_j)\) thỏa \(A_i + A_j = x\)
<=> Với mỗi \(Ai\) tìm số lượng số \(A_j\) thỏa \(x - A_i == A_j\) và loại ra khỏi mảng
Hint 2
Lưu các số và tần số của nó vào một mảng, có thể sử dụng CTDL
std::mapcho đơn giảnĐể loại khỏi mảng, ta có thể thực hiện gán tần_số\((A_j)\) = 0 thay vì duyệt qua và xóa
Hint 3
Công thức tính
- Gọi (nx, fx) là số Ai bất kì và tấn số của nó trong mảng
- Số còn lại là (ny, fy) là số Aj = x - Ai và tần số của nó trong mảng
- Khi nx # ny thì res += fx * fy (có fx cách chọn Ai và fy cách chọn Aj)
- Khi nx = ny thì res += fx * (fx - 1) / 2 (có fx cách chọn Ai và (fx - 1) cách chọn Aj khác Ai)
Reference AC code | O(n log n) time | O(n) auxiliary space | STL, Combinatorics
C++
int main()
{
/// Input
int n = readInt();
int k = readInt();
/// Nhan vao mang bieu dien duoi dang <gia tri, tan so>
map<int, int> M;
while (n--) M[readInt()]++;
ll res = 0;
for (pair<int, int> e : M)
{
/// Tim cap (nx, ny) = (Ai, Aj) thoa (nx + ny = k) va tan so cua no (fx, fy)
int nx = e.first; int fx = e.second;
int ny = k - e.first; int fy = M[ny];
M.erase(ny); /// xoa phan tu khoi mang
if (nx == ny) res += 1LL * fx * (fx - 1) / 2; /// Co (fx cach chon nx va fx - 1 cach chon ny khac nx)
else res += 1LL * fx * fy; /// Co (fx cach chon nx va fy cach chon ny)
}
/// Xuat ket qua
cout << res;
return 0;
}
Bình luận
ngôn ngữ gì đây ta
tại sao lại là (fx-1)/2 v