Hướng dẫn giải của Lời chúc tết

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn, Viet12, LamThanhVu, nquang2909

Hiểu bài toán

Bài toán yêu cầu đếm số lượng các xâu ký tự khác nhau trong danh sách gồm n xâu. Một xâu được coi là khác biệt nếu nó có độ dài khác hoặc chứa ít nhất một ký tự khác nhau ở cùng một vị trí so với các xâu khác. Input bao gồm số nguyên n và n xâu ký tự (chỉ chứa chữ cái in hoa và dấu cách, độ dài tối đa 30).

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

Cách Brute Force (Duyệt kép)

#include <stdio.h>
#include <string.h>

int main() {
    int n;
    scanf("%d", &n);
    getchar(); // Đọc ký tự newline sau số n
    char s[10000][31]; // Mảng lưu các xâu
    int distinct_count = 0;

    // Đọc tất cả các xâu
    for(int i = 0; i < n; i++) {
        fgets(s[i], 31, stdin);
        // Loại bỏ ký tự newline nếu có
        size_t len = strlen(s[i]);
        if(len > 0 && s[i][len - 1] == '\n') {
            s[i][len - 1] = '\0';
        }
    }

    // Kiểm tra từng xâu
    for(int i = 0; i < n; i++) {
        int is_duplicate = 0;
        // So sánh với tất cả các xâu trước đó
        for(int j = 0; j < i; j++) {
            if(strcmp(s[i], s[j]) == 0) {
                is_duplicate = 1;
                break;
            }
        }
        if(!is_duplicate) {
            distinct_count++;
        }
    }

    printf("%d", distinct_count);
    return 0;
}

Time Complexity: O(n^2 * L)
Space Complexity: O(n * L)

Phương pháp này đọc toàn bộ dữ liệu vào mảng, sau đó với mỗi xâu, nó so sánh với tất cả các xâu đã xuất hiện trước đó bằng hàm strcmp. Nếu không tìm thấy xâu trùng lặp, ta tăng biến đếm. Đây là cách tiếp cận trực quan nhất nhưng không hiệu quả về thời gian khi n lớn.

Cách Sử dụng Hash Set (Tối ưu)

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    cin.ignore(); // Bỏ qua ký tự newline

    unordered_set<string> distinct_strings;
    string s;

    for(int i = 0; i < n; i++) {
        getline(cin, s);
        distinct_strings.insert(s);
    }

    cout << distinct_strings.size();
    return 0;
}

Time Complexity: O(n * L)
Space Complexity: O(n * L)

Sử dụng cấu trúc dữ liệu Hash Set (set trong C++) để lưu trữ các xâu. Khi thêm một xâu vào set, nó sẽ tự động bỏ qua nếu xâu đó đã tồn tại. Đây là phương pháp hiệu quả nhất với độ phức tạp thời gian tuyến tính O(n).

Cách Sắp xếp và Đếm

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_strings(const void *a, const void *b) {
    return strcmp(*(const char **)a, *(const char **)b);
}

int main() {
    int n;
    scanf("%d", &n);
    getchar();

    // Cấp phát động để an toàn hơn
    char **s = (char**)malloc(n * sizeof(char*));
    for(int i = 0; i < n; i++) {
        s[i] = (char*)malloc(31 * sizeof(char));
        fgets(s[i], 31, stdin);
        size_t len = strlen(s[i]);
        if(len > 0 && s[i][len-1] == '\n') {
            s[i][len-1] = '\0';
        }
    }

    // Sắp xếp mảng các xâu
    qsort(s, n, sizeof(char*), compare_strings);

    int distinct_count = 0;
    if(n > 0) distinct_count = 1;

    // Đếm số lượng xâu khác nhau sau khi sắp xếp
    for(int i = 1; i < n; i++) {
        if(strcmp(s[i], s[i-1]) != 0) {
            distinct_count++;
        }
    }

    printf("%d", distinct_count);

    // Giải phóng bộ nhớ
    for(int i = 0; i < n; i++) free(s[i]);
    free(s);

    return 0;
}

Time Complexity: O(n log n * L)
Space Complexity: O(n * L)

Đầu tiên, ta sắp xếp tất cả các xâu theo thứ tự từ điển. Sau đó, ta chỉ cần duyệt một lần để đếm các xâu khác nhau (xâu hiện tại khác xâu liền trước). Phương pháp này hiệu quả hơn Brute Force nhưng kém hơn Hash Set một chút về thời gian chạy.

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

Cách tiếp cận	Time	Space	Tên
1	O(n^2 * L)	O(n * L)	Brute Force (Duyệt kép)
2	O(n * L)	O(n * L)	Sử dụng Hash Set (Tối ưu)
3	O(n log n * L)	O(n * L)	Sắp xếp và Đếm

Bài học kinh nghiệm

Bài toán có thể được giải quyết bằng cách loại bỏ các phần tử trùng lặp (deduplication).
Với ràng buộc n <= 10^4, các thuật toán O(n^2) vẫn có thể chạy trong thời gian cho phép nhưng O(n) hoặc O(n log n) là tối ưu hơn.
Sử dụng cấu trúc dữ liệu có sẵn (Set/Hash Map) giúp code ngắn gọn và hiệu quả.

Lỗi thường gặp

Không xử lý ký tự newline ('\n') khi sử dụng fgets hoặc gets, dẫn đến việc so sánh sai (ví dụ: 'A\n' khác với 'A').
Tràn bộ nhớ nếu khai báo mảng quá lớn hoặc sai cách cấp phát động.
Quên getchar() hoặc cin.ignore() sau khi đọc số n để xử lý ký tự newline trước khi đọc chuỗi.

Bình luận

Please read the guidelines before commenting.

Không có bình luận tại thời điểm này.