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

Xem PDF
Tác giả:
admin
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 
4

Bình luận


  • 0
    PY1CLeDongQuan    11:52 a.m. 29 Tháng 4, 2024

    bài khó quá


    • 0
      thinhec12012007    9:51 p.m. 24 Tháng 4, 2024

      Mọi người có thể tham khảo code :

      include <bits/stdc++.h>

      using namespace std;
      map<int,int>mp;

      define ll long long

      int n,k,x;
      ll res=0;
      int main() {
      ios_base::sync_with_stdio(0);
      cin.tie(0);cout.tie(0);
      cin>>n>>k;
      int tam;
      for(int i=1;i<=n;i++) {
      cin>>x;
      mp[x]++;
      tam=k-x;
      if(k-x!=x)
      res+=mp[k-x];

      }
ll gan=mp[k/2];
if(gan>=2) gan--;
else gan=0;

cout<<res+(gan*(gan+1)/2);
return 0;

      }


      • 0
        thinhec12012007    9:51 p.m. 24 Tháng 4, 2024

        Đây là cách giải của mình, bạn nào có thắc mắc hay câu hỏi nào thì có thể hỏi mình ạ
        7 6
        1 2 4 3 4 5 3

        Các cặp số thỏa mãn tổng bằng 6 :
        1-5
        2-4
        2-4
        3-3

        Ta sẽ dùng map để giải bài này : Đầu tiên ta sẽ đếm số lần xuất hiện của các phần tử , sau đó cộng số lần xuất hiện của phần tử thỏa mãn : tổng của phần tử đó cộng một phần tử khác bằng k.
        Ở đây mình sẽ dùng biến đếm tên là res :
        Thì số cặp sẽ thỏa mãn : res+=mp[k-x]; (với x lần lượt là các phần tử trong mảng) .
        Ta có tính chất như sau : một số nào đó + với số x bằng k :
        Thì số đó sẽ có giá trị là : k-x.
        Như vậy ta chỉ cần đếm sự xuất hiện của số k-x nào đó trong mảng là sẽ đếm được số cặp có tổng là k
        Lưu ý ta sẽ không cộng vào phần tử có giá trị là : k/2 vội , vì cộng như vậy ta sẽ bị cộng lặp kết quả trước đó .
        Vì phần tử k/2 là trường hợp đặc biệt nên ta sẽ chia làm 2 trường hợp :
        Nếu phần tử k/2 xuất hiện lớn hơn hoặc bằng 2 lần trong mảng thì ta
        Sẽ có số cặp thỏa mãn là : tổng từ 1 đến k/2-1 số lần xuất hiện của phần tử k/2 đó
        Vd : 4 4 4 4 và tổng cần tìm là 8
        Thì ta sẽ có số cặp thỏa mãn là : 6 => tương đương tổng từ 1 đến 3 là 6
        Ngược lại nếu không có giá trị nào bằng k/2 trong mảng thì ta không cần cộng vào :
         Và kết quả cuối cùng là kết quả của : số cặp có giá trị là k/2 và res.


        • -5
          blinh    8:36 p.m. 31 Tháng 3, 2024

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


          • 0
            Green    4:32 p.m. 25 Tháng 11, 2023 ← đã chỉnh sửa
            hint

            bài này có 2 cách:
            -Cách 1 dành cho ai làm trâu ta sẽ duyệt mảng như bình thường và xét trường hợp nếu như biến ta cứ cho là n mà bằng với tổng mảng a[i]+a[j] thì ta sẽ đăng biến đếm lên cách này thì sẽ dẫn đến bị tle
            -Cách 2 thì dùng hàm chặt có sẵn là ac


            • 0
              dinhthangnee    12:30 a.m. 19 Tháng 11, 2023

              Spoiler Alert

              1. Do dữ liệu cho \(10^5\) nên ta sắp xếp lại mảng rồi duyệt từng phần tử Ai, với mỗi phần tử ta tìm xem có bao nhiêu phần tử x - Ai. Kết quả nhớ chia đôi nếu duyệt cả mảng
                Lưu ý trường hợp 2 * Ai = x :>
              2. Do \(0 < x \leqslant 10^6\) nên đếm phân phối bằng mảng oke, tội là phần tử nào lớn hơn thì vứt. :>. Ai muốn đếm bằng unordered_map cũng ổn nhe

              • -4
                Sang522008    11:20 p.m. 3 Tháng 2, 2023

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

                1 phản hồi

                • 0
                  minhtuanitk20    12:35 p.m. 13 Tháng 10, 2021

                  hint 1 là nhanh nhất r

                  1 phản hồi

                  • -3
                    vanlatuiday    9:57 p.m. 18 Tháng 8, 2021 ← đã chỉnh sửa

                    hmm


                    • 40
                      SPyofgame    5:49 a.m. 11 Tháng 6, 2020 ← chỉnh sửa 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

                      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;
}
                      2 phản hồi