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

View as PDF

Submit solution


Points: 400 (partial)
Time limit: 1.0s
Memory limit: 977M
Input: stdin
Output: stdout

Author:
Problem type

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^9n≤ 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
4

Comments


  • 0
    Sang522008  commented on 11:20 p.m. 3 feb, 2023

    a ơi pas e chạy dc mà nộp bị lỗi phân khúc do sao ạ


  • 0
    minhtuanitk20  commented on 12:35 p.m. 13 oct, 2021

    hint 1 là nhanh nhất r


  • -2
    vanlatuiday  commented on 9:57 p.m. 18 aug, 2021 edited

    hmm


  • 31
    SPyofgame  commented on 5:49 a.m. 11 jun, 2020 edit 2

    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

    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  commented on 9:53 a.m. 5 oct, 2021 edit 3

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


      • 9
        SPyofgame  commented on 2:07 p.m. 5 oct, 2021 edited

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


        • 0
          lagiahuy  commented on 10:49 a.m. 16 oct, 2021

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


        • 0
          lagiahuy  commented on 5:44 p.m. 8 oct, 2021 edited

          (đã thu hồi)


          • 1
            SPyofgame  commented on 12:58 a.m. 9 oct, 2021

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


            • -6
              lagiahuy  commented on 8:14 p.m. 9 oct, 2021 edited

              This comment is hidden due to too much negative feedback. Click here to view it.


              • 1
                SPyofgame  commented on 10:06 p.m. 9 oct, 2021

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

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

                • -1
                  lagiahuy  commented on 9:09 a.m. 11 oct, 2021

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


    • 5
      Lê_Gia_Khánh  commented on 4:33 p.m. 1 jul, 2020

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


      • 1
        SPyofgame  commented on 2:07 p.m. 5 oct, 2021

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


      • -9
        nguyenquochuy  commented on 8:01 p.m. 26 sep, 2020

        This comment is hidden due to too much negative feedback. Click here to view it.