Hướng dẫn giải của Chuẩn hoá

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, hhieu474, 404, Dracognium

Hiểu bài toán

Bài toán yêu cầu viết một chương trình chuẩn hóa chuỗi dựa trên loại lệnh được cung cấp. Input bao gồm số lượng test case t và t dòng tiếp theo. Mỗi dòng chứa một lệnh (TEN, CHUOI, THAY, SORCE1, SORCE2) và một chuỗi ký tự.

Các loại chuẩn hóa:

  1. TEN: Viết hoa chữ cái đầu mỗi từ, viết thường các chữ cái còn lại, và loại bỏ khoảng trắng thừa. Ví dụ: nguyen van nAm -> Nguyen Van Nam.
  2. CHUOI: Chỉ loại bỏ khoảng trắng thừa giữa các từ, giữ nguyên ký tự. Ví dụ: Chao cac coder -> Chao cac coder.
  3. THAY: Loại bỏ khoảng trắng, sau đó thêm chuỗi @gmail.com vào cuối. Ví dụ: ngUyeNvAnA -> [email protected].
  4. SORCE1: Chuyển tất cả ký tự về chữ thường và loại bỏ khoảng trắng. Ví dụ: Chaocac -> chaocac.
  5. SORCE2: Chuyển tất cả ký tự về chữ hoa và loại bỏ khoảng trắng. Ví dụ: chaocac -> CHAOCAC.

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

Cách Sử dụng stringstream và xử lý từng từ
#include <iostream>
#include <string>
#include <sstream>
#include <cctype>
#include <algorithm>

using namespace std;

void process(string command, string s) {
    if (command == "TEN") {
        stringstream ss(s);
        string word, res = "";
        while (ss >> word) {
            if (!res.empty()) res += " ";
            word[0] = toupper(word[0]);
            for (int i = 1; i < word.length(); i++) {
                word[i] = tolower(word[i]);
            }
            res += word;
        }
        cout << res << endl;
    } else if (command == "CHUOI") {
        stringstream ss(s);
        string word, res = "";
        while (ss >> word) {
            if (!res.empty()) res += " ";
            res += word;
        }
        cout << res << endl;
    } else if (command == "THAY") {
        stringstream ss(s);
        string word, res = "";
        while (ss >> word) res += word;
        cout << res << "@gmail.com" << endl;
    } else if (command == "SORCE1") {
        stringstream ss(s);
        string word, res = "";
        while (ss >> word) res += word;
        transform(res.begin(), res.end(), res.begin(), ::tolower);
        cout << res << endl;
    } else if (command == "SORCE2") {
        stringstream ss(s);
        string word, res = "";
        while (ss >> word) res += word;
        transform(res.begin(), res.end(), res.begin(), ::toupper);
        cout << res << endl;
    }
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)

Phương pháp này sử dụng stringstream để tự động tách chuỗi input thành các từ dựa trên khoảng trắng.

  • Đối với TEN: Duyệt qua từng từ, viết hoa ký tự đầu và viết thường các ký tự còn lại.
  • Đối với CHUOI: Duyệt và nối các từ lại với nhau, stringstream đã tự động loại bỏ khoảng trắng thừa.
  • Đối với THAY, SORCE1, SORCE2: Duyệt và nối các từ (hoặc xóa khoảng trắng), sau đó thực hiện biến đổi ký tự và thêm hậu tố nếu cần. Cách này dễ hiểu và xử lý đúng các yêu cầu về khoảng trắng.
Cách Xử lý trực tiếp chuỗi (Manual String Processing)
#include <iostream>
#include <string>
#include <cctype>

using namespace std;

int main() {
    int t;
    cin >> t;
    cin.ignore();
    while (t--) {
        string cmd, s;
        cin >> cmd;
        getline(cin, s);
        if (s.length() > 0 && s[0] == ' ') s.erase(0, 1);

        if (cmd == "TEN") {
            if (s.length() > 0) s[0] = toupper(s[0]);
            bool isSpace = false;
            for (int i = 1; i < s.length(); i++) {
                if (s[i] == ' ') {
                    isSpace = true;
                } else {
                    if (isSpace) {
                        s[i] = toupper(s[i]);
                        isSpace = false;
                    } else {
                        s[i] = tolower(s[i]);
                    }
                }
            }
            cout << s << endl;
        } else if (cmd == "CHUOI") {
            string res = "";
            bool space = false;
            for (char c : s) {
                if (c != ' ') {
                    if (space) res += ' ';
                    res += c;
                    space = false;
                } else {
                    space = true;
                }
            }
            cout << res << endl;
        } else if (cmd == "THAY") {
            for (char c : s) if (c != ' ') cout << c;
            cout << "@gmail.com" << endl;
        } else if (cmd == "SORCE1") {
            for (char c : s) if (c != ' ') cout << (char)tolower(c);
            cout << endl;
        } else if (cmd == "SORCE2") {
            for (char c : s) if (c != ' ') cout << (char)toupper(c);
            cout << endl;
        }
    }
    return 0;
}
  • Time Complexity: O(N)
  • Space Complexity: O(1) (không tạo string mới, output trực tiếp)

Cách tiếp cận này không dùng stringstream mà duyệt qua từng ký tự của chuỗi.

  • TEN: Duyệt và theo dõi trạng thái (liệu ký tự trước đó có phải là khoảng trắng không) để quyết định viết hoa hay viết thường.
  • CHUOI: Duyệt và chỉ in ra ký tự nếu nó không phải khoảng trắng, hoặc nếu là khoảng trắng thì chỉ in khi gặp từ tiếp theo (tránh in nhiều khoảng trắng).
  • Các loại còn lại: Duyệt và in ra hoặc biến đổi ký tự ngay lập tức, bỏ qua khoảng trắng. Cách này hiệu quả về bộ nhớ hơn một chút và nhanh hơn do tránh việc tạo các object stringstream lặp lại.
Cách Phân loại theo Logic
#include <iostream>
#include <string>
#include <cctype>
#include <vector>

using namespace std;

int main() {
    int t;
    cin >> t;
    cin.ignore();
    while(t--) {
        string type, line;
        cin >> type;
        getline(cin, line);

        // Xử lý loại bỏ khoảng trắng thừa
        string clean_str = "";
        bool space = false;
        for(char c : line) {
            if(c != ' ') {
                if(space) clean_str += ' ';
                clean_str += c;
                space = false;
            } else {
                space = true;
            }
        }

        if(type == "TEN") {
            for(int i = 0; i < clean_str.size(); ++i) {
                if(i == 0 || clean_str[i-1] == ' ') clean_str[i] = toupper(clean_str[i]);
                else clean_str[i] = tolower(clean_str[i]);
            }
            cout << clean_str << endl;
        }
        else if(type == "CHUOI") {
            cout << clean_str << endl;
        }
        else if(type == "THAY") {
            for(char c : clean_str) if(c != ' ') cout << c;
            cout << "@gmail.com" << endl;
        }
        else if(type == "SORCE1") {
            for(char c : clean_str) cout << (char)tolower(c);
            cout << endl;
        }
        else if(type == "SORCE2") {
            for(char c : clean_str) cout << (char)toupper(c);
            cout << endl;
        }
    }
    return 0;
}
  • Time Complexity: O(N)
  • Space Complexity: O(N)

Đây là sự kết hợp giữa việc chuẩn hóa khoảng trắng trước (giống CHUOI) và áp dụng các quy tắc cụ thể sau đó. Bước đầu tiên luôn là loại bỏ khoảng trắng thừa.

  • Sau đó, TEN thực hiện biến đổi casing dựa trên vị trí.
  • CHUOI in ra chuỗi đã xử lý khoảng trắng.
  • Các lệnh khác (THAY, SORCE1, SORCE2) xóa hoàn toàn khoảng trắng và thực hiện biến đổi. Cách này giúp code gọn gàng hơn khi các lệnh đều dựa trên cùng một chuỗi 'sạch'.

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

Cách tiếp cận Time Space Tên
1 O(N) O(N) Sử dụng stringstream và xử lý từng từ
2 O(N) O(1) (không tạo string mới, output trực tiếp) Xử lý trực tiếp chuỗi (Manual String Processing)
3 O(N) O(N) Phân loại theo Logic

Bài học kinh nghiệm

  • Lệnh TEN yêu cầu xử lý khoảng trắng: khoảng trắng là dấu hiệu để viết hoa chữ cái đầu từ tiếp theo, nhưng không được loại bỏ.
  • Lệnh CHUOI chỉ loại bỏ khoảng trắng thừa (2 khoảng trắng trở lên thành 1), giữ lại các từ.
  • Các lệnh THAY, SORCE1, SORCE2 đều yêu cầu loại bỏ hoàn toàn khoảng trắng giữa các từ.
  • Input có thể chứa nhiều khoảng trắng ở đầu/cuối hoặc giữa các từ, cần xử lý kỹ.

Lỗi thường gặp

  • Quên bỏ ký tự newline sau khi đọc số t hoặc sau khi dùng cin >>, gây lỗi cho getline sau đó.
  • Xử lý sai quy tắc 'viết hoa chữ cái đầu từ' của TEN nếu chỉ đơn giản kiểm tra i == 0 mà không kiểm tra ký tự trước đó có phải là khoảng trắng không (đối với các từ ở giữa chuỗi).
  • In ra khoảng trắng thừa ở cuối chuỗi output.
  • Đối với THAY, SORCE1, SORCE2, nếu chỉ dùng stringstream để tách từ rồi nối lại, cần đảm bảo không dùng stringstream để in trực tiếp nếu yêu cầu là xóa hết khoảng trắng (ví dụ SORCE1 yêu cầu chaocaccoder chứ không phải chaocac coder).

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.