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

Tác giả:

Dạng bài

Điểm: 1500 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

Cho dãy số \(A\) gồm \(n\) phần tử nguyên dương \(A_1,A_2,…,A_n\). Mỗi phần tử có giá trị không vượt quá \(10^9\) và \(n≤ 10^5\). Một cặp số được gọi là cặp tương đồng với \(x\), nếu cặp số này có tổng bằng số \(x\) cho trước nào đó.

Yêu cầu: Hãy đếm xem trong dãy số \(A\) có bao nhiêu cặp số (\(A_i;A_j\)) tương đồng với \(x\) (có nghĩa là \(A_i+ A_j=x\)) với \(i<j\).

Input

Dòng đầu tiên chứa dãy số \(n,x\) (\(n≤10^5,x≤10^6\)).
Dòng thứ 2 chứa \(n\) phần tử của dãy số \(A\) (\(A_i≤10^9\)).

Output

Ghi ra một số nguyên là cặp đôi tương đồng của dãy số.

Example

Test 1

Input

7 6
1 2 4 3 4 5 3

Output

Bình luận

`Spoiler Alert`

Hint 1

Đề yêu cầu (Ai, Aj) thỏa Ai + Aj = x

<=> Với mỗi Ai tìm số lượng số Aj thỏa x - Ai == Aj 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ố(Aj) = 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;
}

-3

lagiahuy 9:53 a.m. 5 Tháng 10, 2021 ← chỉnh sửa 3 →

Mình bị lỗi phân đoạn, có bình thường không vậy?!

10

SPyofgame 2:07 p.m. 5 Tháng 10, 2021 ← đã chỉnh sửa →

Bạn thử C++23 hay C++26 chưa 🐧

0

lagiahuy 10:49 a.m. 16 Tháng 10, 2021

bạn ơi mình có cập nhật lỗi rồi, phía trên nha bạn

0

lagiahuy 5:44 p.m. 8 Tháng 10, 2021 ← đã chỉnh sửa →

(đã thu hồi)

2

SPyofgame 12:58 a.m. 9 Tháng 10, 2021

readInt() là hàm nhận một số nguyên thôi bạn ạ

-4

lagiahuy 8:14 p.m. 9 Tháng 10, 2021 ← đã chỉnh sửa →

(đã thu hồi)

Mình xin lỗi nhé, ý mình là

C++

int readInt()
{
    int x;
    cin >> x;
    return x;
}

-3

lagiahuy 9:09 a.m. 11 Tháng 10, 2021

được rồi, chuẩn luôn

9

Lê_Gia_Khánh 4:33 p.m. 1 Tháng 7, 2020

Còn 1 cách nhanh hơn là đếm phân phối ấy anh

4

SPyofgame 2:07 p.m. 5 Tháng 10, 2021

Ah uk, lúc đầu anh không để ý kĩ

-15

nguyenquochuy 8:01 p.m. 26 Tháng 9, 2020

phân phối như nào người ae thiện lành .-.

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

3

obamagaming 1:28 p.m. 28 Tháng 4, 2023

Giới hạn của Ai <= 10^9 nhưng giới hạn của x <= 10^6 mà cần tìm Ai+Aj = x nên các số thỏa mãn sẽ phải nhỏ hơn x, khi đó thì đpp mảng 1e6 ổn nhất rồi

9 bình luận nữa