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.

Authors: SPyofgame

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::map cho đơ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