Hướng dẫn cho Cặp số đặc biệt

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho dãy số nguyên dương \(A_1, A_2, \dots, A_n\). Một cặp số \((X, Y)\) được gọi là đặc biệt nếu:

Số lượng chữ số chẵn của \(X\) bằng số lượng chữ số lẻ của \(Y\).
Số lượng chữ số lẻ của \(X\) bằng số lượng chữ số chẵn của \(Y\).

Yêu cầu: Đếm số lượng cặp \((A_i, A_j)\) với \(i \neq j\) là cặp số đặc biệt. Lưu ý rằng \((A_i, A_j)\) và \((A_j, A_i)\) được tính là hai cặp khác nhau.

Phân tích

Điều kiện: \(n \leq 10^5\), \(A_i \leq 10^{10}\).
Nhận xét 1: Một số \(A_i\) có tối đa 11 chữ số (vì \(A_i \leq 10^{10}\)). Do đó, số lượng chữ số chẵn và lẻ của mỗi số chỉ nằm trong khoảng từ 0 đến 11.
Nhận xét 2: Gọi \(even(X)\) là số chữ số chẵn của \(X\) và \(odd(X)\) là số chữ số lẻ của \(X\). Cặp \((X, Y)\) đặc biệt khi và chỉ khi:
- \(even(X) = odd(Y)\)
- \(odd(X) = even(Y)\)
Nhận xét 3: Đề bài yêu cầu đếm cặp có thứ tự \((i, j)\) với \(i \neq j\). Nếu ta tìm được số lượng cặp không thứ tự \(\{i, j\}\) thỏa mãn, ta chỉ cần nhân đôi kết quả.

Cách làm đơn giản (Brute Force)

Ý tưởng

Duyệt qua mọi cặp \((i, j)\) với \(1 \leq i < j \leq n\). Với mỗi cặp, ta đếm số chữ số chẵn/lẻ của \(A_i\) và \(A_j\) rồi kiểm tra điều kiện.

Độ phức tạp

Thời gian: \(O(n^2 \times \log_{10}(\max A_i))\)
Đánh giá: Với \(n = 10^5\), \(n^2 = 10^{10}\), cách này sẽ bị quá thời gian (TLE). Cách này chỉ phù hợp với \(n \leq 5000\).

Code Brute Force

C++

#include <bits/stdc++.h>
using namespace std;

struct DigitCount {
    int odd, even;
};

DigitCount countDigits(long long n) {
    int odd = 0, even = 0;
    if (n == 0) return {0, 1};
    while (n > 0) {
        if ((n % 10) % 2 == 0) even++;
        else odd++;
        n /= 10;
    }
    return {odd, even};
}

int main() {
    int n; cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];

    long long count = 0;
    for (int i = 0; i < n; i++) {
        DigitCount d1 = countDigits(a[i]);
        for (int j = i + 1; j < n; j++) {
            DigitCount d2 = countDigits(a[j]);
            if (d1.even == d2.odd && d1.odd == d2.even) {
                count++;
            }
        }
    }
    cout << count * 2;
    return 0;
}

Python

def count_digits(n):
    odd, even = 0, 0
    for char in str(n):
        if int(char) % 2 == 0:
            even += 1
        else:
            odd += 1
    return odd, even

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    o1, e1 = count_digits(a[i])
    for j in range(i + 1, n):
        o2, e2 = count_digits(a[j])
        if e1 == o2 and o1 == e2:
            ans += 1
print(ans * 2)

Hướng giải quyết (Tối ưu)

Ý tưởng

Thay vì duyệt mọi cặp, ta sử dụng một mảng tần suất (hoặc bảng băm) để lưu trữ số lượng các số có cùng bộ \((odd, even)\).

Gọi \(cnt[o][e]\) là số lượng số đã duyệt qua có \(o\) chữ số lẻ và \(e\) chữ số chẵn.
Khi duyệt đến số \(A_i\), ta tính được \(odd(A_i)\) và \(even(A_i)\).
Theo điều kiện bài toán, \(A_i\) sẽ tạo thành cặp đặc biệt với các số \(A_j\) đã duyệt trước đó nếu \(odd(A_j) = even(A_i)\) và \(even(A_j) = odd(A_i)\).
Số lượng số \(A_j\) như vậy chính là giá trị đang được lưu tại \(cnt[even(A_i)][odd(A_i)]\).
Sau khi cộng dồn vào kết quả, ta cập nhật \(cnt[odd(A_i)][even(A_i)]\) thêm 1 để phục vụ cho các số phía sau.

Các bước thực hiện

Khởi tạo mảng cnt[12][12] bằng 0.
Duyệt qua từng số \(A_i\) trong dãy:
- Đếm số chữ số lẻ \(o\) và chẵn \(e\) của \(A_i\).
- Cộng cnt[e][o] vào biến kết quả ans.
- Tăng cnt[o][e] lên 1 đơn vị.
Kết quả cuối cùng là ans * 2 (do đề bài tính cặp \((i, j)\) và \((j, i)\) là khác nhau).

Độ phức tạp

Thời gian: \(O(n \times \log_{10}(\max A_i))\), trong đó \(\log_{10}(\max A_i) \leq 11\). Với \(n = 10^5\), thuật toán chạy rất nhanh.
Bộ nhớ: \(O(12 \times 12)\) để lưu mảng tần suất, không đáng kể.

Code tham khảo

C++

#include <bits/stdc++.h>
using namespace std;

// Sử dụng long long để tránh tràn số khi n lớn
long long cnt[12][12];

pair<int, int> countDigit(long long n) {
    int od = 0, ev = 0;
    // Xử lý trường hợp n = 0 nếu đề bài cho phép (đề bài này là số nguyên dương)
    if (n == 0) return {0, 1};
    while (n > 0) {
        if ((n % 10) % 2 != 0)
            od++;
        else
            ev++;
        n /= 10;
    }
    return {od, ev};
}

int main() {
    // Tối ưu tốc độ nhập xuất
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    long long total_pairs = 0;

    for (int i = 0; i < n; i++) {
        long long ai;
        cin >> ai;
        pair<int, int> p = countDigit(ai);
        int odd = p.first;
        int even = p.second;

        // Tìm các số đã duyệt trước đó thỏa mãn: 
        // odd_j = even_i và even_j = odd_i
        total_pairs += cnt[even][odd];

        // Lưu số hiện tại vào bảng tần suất
        cnt[odd][even]++;
    }

    // Nhân 2 vì cặp (Ai, Aj) và (Aj, Ai) tính là khác nhau
    cout << total_pairs * 2 << endl;

    return 0;
}

Python

import sys

def count_digit(n):
    odd, even = 0, 0
    if n == 0:
        return 0, 1
    while n > 0:
        if (n % 10) % 2 != 0:
            odd += 1
        else:
            even += 1
        n //= 10
    return odd, even

def solve():
    # Đọc dữ liệu từ stdin để nhanh hơn
    input_data = sys.stdin.read().split()
    if not input_data:
        return

    n = int(input_data[0])
    a = input_data[1:]

    # cnt[odd][even]
    cnt = [[0] * 12 for _ in range(12)]
    total_pairs = 0

    for i in range(n):
        num = int(a[i])
        odd, even = count_digit(num)

        # Kiểm tra điều kiện: odd_j = even_i và even_j = odd_i
        total_pairs += cnt[even][odd]

        # Cập nhật bảng tần suất
        cnt[odd][even] += 1

    print(total_pairs * 2)

if __name__ == "__main__":
    solve()

Bình luận

Tải bình luận...

Không có bình luận nào.