Editorial for Đếm cặp đôi (HSG'20)

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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;
}

Comments

There are no comments at the moment.