Hiểu bài toán

Bài toán yêu cầu xử lý hai nhiệm vụ: (1) Đọc một mảng gồm n số nguyên, đếm tần suất xuất hiện của từng giá trị. (2) Trả lời q truy vấn, mỗi truy vấn yêu cầu trả về số lần xuất hiện của một giá trị x cụ thể trong mảng ban đầu. Nói cách khác, với mỗi số x được hỏi, ta cần in ra số lượng phần tử có giá trị bằng x trong mảng.

Các cách tiếp cận

Cách Sử dụng Map

#include <iostream>
#include <map>
#include <fstream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ifstream fi("lucky.inp");
    ofstream fo("lucky.out");

    int n;
    fi >> n;
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        int x;
        fi >> x;
        mp[x]++; // Tăng tần suất của x
    }

    int q;
    fi >> q;
    while (q--) {
        int x;
        fi >> x;
        fo << mp[x] << "\n"; // In ra tần suất (0 nếu không tồn tại)
    }

    fi.close();
    fo.close();
    return 0;
}

• Time Complexity: O((n + q) log n)
• Space Complexity: O(n)

Sử dụng cấu trúc dữ liệu std::map của C++ để lưu trữ tần suất. map là một cấu trúc cây đỏ-đen, cho phép lưu trữ các cặp (key, value) và truy cập theo key trong thời gian O(log n).

• Bước 1: Đọc n và lặp n lần để đọc các số. Với mỗi số x, thực hiện mp[x]++. Nếu x chưa có trong map, nó sẽ được tạo với giá trị 0 rồi tăng lên 1.
• Bước 2: Đọc q và lặp q lần để xử lý truy vấn. Với mỗi truy vấn x, ta chỉ cần truy cập mp[x] để lấy giá trị.
• Ưu điểm: Dễ dàng cài đặt, tự động sắp xếp key tăng dần, hỗ trợ các số âm/bất kỳ.
• Nhược điểm: Tốc độ truy cập chậm hơn unordered_map một chút do phải đi qua cây.

Cách Sử dụng Hash Map (Unordered Map)

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    freopen("LUCKY.INP", "r", stdin);
    freopen("LUCKY.OUT", "w", stdout);

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

    unordered_map<long long, int> freq;
    for(int i = 0; i < n; i++) freq[A[i]]++;

    int Q;
    cin >> Q;
    for(int i = 0; i < Q; i++){
        long long x;
        cin >> x;
        cout << freq[x] << "\n";
    }

    return 0;
}

• Time Complexity: O(n + q) trung bình
• Space Complexity: O(n)

Sử dụng std::unordered_map (cấu trúc dữ liệu dạng băm/dictionary). Khác với map dùng cây, unordered_map dùng bảng băm.

• Cách hoạt động tương tự map: Đọc dữ liệu và tăng tần suất freq[x]++. Với mỗi truy vấn, trả về freq[x].
• Ưu điểm: Tốc độ truy cập trung bình là O(1), nhanh hơn O(log n) của map, đặc biệt hiệu quả khi n và q lớn.
• Nhược điểm: Không sắp xếp key, tiêu tốn bộ nhớ nhiều hơn do bảng băm, và worst-case có thể bị tấn công để tạo va chạm (dù trong thi cử hiếm khi xảy ra).

Cách Giả lập (Simulation)

#include <iostream>
#include <vector>
#include <fstream>
using namespace std;

int main() {
    ifstream fi("lucky.inp");
    ofstream fo("lucky.out");

    int n;
    fi >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        fi >> a[i];
    }

    int q;
    fi >> q;
    while (q--) {
        int x, count = 0;
        fi >> x;
        for (int val : a) {
            if (val == x) count++;
        }
        fo << count << "\n";
    }

    fi.close();
    fo.close();
    return 0;
}

• Time Complexity: O(n * q)
• Space Complexity: O(n)

Đây là cách giải quyết trực tiếp nhất (Brute Force) mà không cần dùng cấu trúc dữ liệu phức tạp.

• Bước 1: Đọc toàn bộ mảng n số vào một vector.
• Bước 2: Với mỗi truy vấn x, duyệt toàn bộ vector để đếm số lượng phần tử bằng x.
• Ưu điểm: Dễ hiểu, không cần kiến thức về map.
• Nhược điểm: Rất chậm. Nếu n=10^5 và q=10^5, thời gian chạy sẽ khoảng 10^10 thao tác, dẫn đến lỗi quá thời gian (Time Limit Exceeded).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là bài toán đếm tần suất cơ bản, yêu cầu tách biệt quá trình tiền xử lý (đọc mảng, đếm tần suất) và quá trình truy vấn.
• Sử dụng Hash Map (Unordered Map) là phương án tối ưu nhất về tốc độ trong hầu hết các trường hợp cho các bài toán tương tự với dữ liệu lớn.
• Các giải pháp Accepted đều sử dụng luồng file (freopen/fstream) để đọc ghi dữ liệu, đây là yêu cầu tiêu chuẩn trong các kỳ thi lập trình thi đấu.

Lỗi thường gặp

• Quên khai báo ios_base::sync_with_stdio(false); cin.tie(0); hoặc freopen dẫn đến việc đọc ghi chậm hoặc sai định dạng file input/output.
• Sử dụng phương pháp duyệt mảng lặp lại cho mỗi truy vấn (O(n*q)) sẽ bị Time Limit Exceeded với dữ liệu lớn.
• Lỗi type dữ liệu: Nếu giá trị số quá lớn (trên 2 tỷ) hoặc âm lớn, cần dùng long long thay vì int (Solution 2 đã dùng long long).