Cặp số đặc biệt
Xem PDF
Điểm:
100 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Hôm nay Nhật học toán trên lớp về chủ đề số đặc biệt. Thầy giáo định nghĩa một số nguyên dương \(x\) bất kì là số đặc biệt nếu như các chữ số của \(x\) đều giống nhau. Ví dụ: \(22, 3333, 1\) là số đặc biệt, còn \(123, 96, 1801\) không phải là số đặc biệt.
Cho dãy số \(A\) gồm \(n\) phần tử \(a_1, a_2, \dots, a_n\). Hãy đếm số cặp chỉ số \((i, j)\) sao cho:
- \(1 ≤ i < j ≤ n\)
- \(a_i + a_j\) là một số đặc biệt
Input
- Dòng đầu chứa số nguyên dương \(n\) \((1 ≤ n ≤ 2 * 10^5)\)
- Dòng tiếp theo chứa \(n\) số nguyên không âm \(a_1, a_2, \dots, a_n\) \((1 ≤ a_i ≤ 10^6)\)
Output
- In ra số cặp chỉ số cần tìm.
Example
Test 1
Input
5
1 2 3 4 5 Output
10
Bình luận
hàng đợi 2 đầu + mảng đếm phân phối(không phải map) = ac
Mình xin chia sẻ lời giải bài này như sau:
Đầu tiên dựa vào tính chất của số đặc biệt. Vì \(a_i\sim 10^6\) nên có thể dễ dàng tìm được tập số đặc biệt như sau: \(S=\){\(1,11,111,....,9999999\)}. Và tập này có \(63\) số.
Tiếp theo bài toán quy về: Cho trước một số \(Q\) và một mảng \(a\) gồm \(n\) phần tử. Hỏi có bao nhiêu cặp (không lặp) thoả mãn tổng của chúng bằng \(Q\).
Đây là một bài toán quen thuộc. Đơn giản ta dùng một mảng để lưu tần số của từng phần tử trong mảng, và sử dụng kĩ thuật đếm bình thường là có thể giải quyết bài toán.
Mình xin lấy một ví dụ để các bạn hình dung rõ hơn:
Cho trước mảng \(a\) gồm \(4\) phần tử: \(1,1,2,2\) và số \(Q=3\). Hỏi có bao nhiêu cặp (không lặp) thoả mãn yêu cầu bài toán.
Bước 1: Ta tạo ra mảng f. Mảng này có chức năng lưu tần số của từng phần tử trong mảng. Ở đây ta có: f[1]=2,f[2]=2.
Bước 2: Ta sẽ duyệt từng phần tử \(a_i\) trong mảng và đếm xem có bao nhiêu phần tử \(a_j(i\ne j)\) thoả mãn \(a_i+a_j=3\). Và kết quả chính là \(f[3-a[i]]\).
Và ta chỉ việc cộng tất cả các kết quả của bước 2 lại. Sau đó chia cho \(2\). Vì mỗi lần lặp qua hết các phần tử của mảng, thì số cặp thoả mãn sẽ bị lặp 2 lần.
Như vậy ta đã giải quyết xong bài toán. Độ phức tạp là: \(O(63*n)\)
Ps: Khi giải bài này, mình rút ra mình số kinh nghiệm sau: Việc dùng map,unordered_map để lưu tần số có vẻ tốn time hơn dùng mảng thông thường.
Các bạn có thể xem code của mình tại đây
Ps: Nếu có gì khó hiểu, các bạn cứ comment
...
Author ơi cho mik xin giới hạn N với a[i] với ạ :v