Hướng dẫn giải của Tách số - LS

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, Dieter, hoanglamnguyen03092014, chaos

Hiểu bài toán

Bài toán yêu cầu từ một chuỗi đầu vào chứa các ký tự số và ký tự phân cách (không phải số), ta cần trích xuất tất cả các số nguyên xuất hiện theo thứ tự tự nhiên. Sau đó, in ra các số này theo hai yêu cầu:

  1. Dòng 1: In các số theo thứ tự xuất hiện ban đầu trong chuỗi.
  2. Dòng 2: In các số sau khi đã sắp xếp tăng dần. Lưu ý quan trọng: Các số có thể có chữ số dẫn đầu là '0' (ví dụ '001', '05'). Trong quá trình xử lý, ta cần chuẩn hóa các số này (loại bỏ số 0 vô nghĩa ở đầu) trước khi so sánh và in ra. Tuy nhiên, khi in ra số 0, ta phải in chính xác "0".

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

Cách Xử lý chuỗi cơ bản với số nguyên
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <cctype>

using namespace std;

int main() {
    ifstream fin("TACHSO.INP");
    ofstream fout("TACHSO.OUT");

    string s;
    getline(fin, s);

    vector<long long> numbers;
    string temp = "";

    // Tách và chuyển đổi sang số
    for (char c : s) {
        if (isdigit(c)) {
            temp += c;
        } else {
            if (!temp.empty()) {
                long long num = stoll(temp); // stoll tự động xử lý số 0 đầu
                numbers.push_back(num);
                temp = "";
            }
        }
    }
    if (!temp.empty()) {
        long long num = stoll(temp);
        numbers.push_back(num);
    }

    // Dòng 1: Xuất hiện
    for (size_t i = 0; i < numbers.size(); i++) {
        if (i > 0) fout << " ";
        fout << numbers[i];
    }
    fout << endl;

    // Dòng 2: Sắp xếp
    sort(numbers.begin(), numbers.end());
    for (size_t i = 0; i < numbers.size(); i++) {
        if (i > 0) fout << " ";
        fout << numbers[i];
    }
    fout << endl;

    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Cách tiếp cận này sử dụng long long để lưu trữ các số.

  1. Duyệt chuỗi, dùng một biến tạm temp để nối các ký tự số.
  2. Khi gặp ký tự không phải số, dùng stoll (string to long long) để chuyển temp thành số và lưu vào vector.
  3. In ra thứ tự xuất hiện.
  4. Dùng hàm sort của C++ để sắp xếp và in ra.

Hạn chế: Nếu các số quá lớn (vượt quá 18-19 chữ số), long long sẽ bị tràn số (overflow) và lỗi. Tuy nhiên, với các kỳ thi thông thường, dữ liệu thường nằm trong giới hạn này.

Cách Xử lý chuỗi dạng số lớn (Big Integer)
#include <bits/stdc++.h>
using namespace std;

// Chuẩn hóa số: xóa số 0 ở đầu. Nếu toàn 0 thì để lại một chữ số "0".
void fix(string &digit) {
    reverse(digit.begin(), digit.end());
    while (!digit.empty() && digit.back() == '0') {
        digit.pop_back();
    }
    if (digit.empty()) digit = "0";
    else reverse(digit.begin(), digit.end()); // Chỉ reverse lại nếu không rỗng
}

// So sánh 2 số lớn dạng chuỗi
bool cmp(string s, string t) {
    if (s.size() != t.size()) return s.size() < t.size();
    return s < t;
}

int main() {
    ifstream fin("TACHSO.INP");
    ofstream fout("TACHSO.OUT");

    string line;
    getline(fin, line);

    vector<string> nums;
    string digit = "";

    // Tách chuỗi
    for (char c : line) {
        if (c >= '0' && c <= '9') {
            digit += c;
        } else {
            if (!digit.empty()) {
                fix(digit); // Chuẩn hóa ngay khi tách
                nums.push_back(digit);
                digit = "";
            }
        }
    }
    if (!digit.empty()) {
        fix(digit);
        nums.push_back(digit);
    }

    // In thứ tự xuất hiện
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0) fout << " ";
        fout << nums[i];
    }
    fout << "\n";

    // Sắp xếp và in
    sort(nums.begin(), nums.end(), cmp);
    for (int i = 0; i < nums.size(); i++) {
        if (i > 0) fout << " ";
        fout << nums[i];
    }

    return 0;
}
  • Time Complexity: O(N * L log N)
  • Space Complexity: O(N * L)

Để giải quyết vấn đề tràn số, ta xử lý các số hoàn toàn dưới dạng chuỗi (string).

  1. Tách các dãy số khỏi chuỗi đầu vào.
  2. Viết hàm fix để loại bỏ các số 0 ở đầu (ví dụ "001" -> "1", "000" -> "0").
  3. Viết hàm cmp để so sánh hai số lớn: so sánh độ dài trước, nếu bằng độ dài thì so sánh theo thứ tự từ điển (lexicographical).
  4. In ra theo thứ tự xuất hiện và sau khi sắp xếp.

Cách này xử lý được số có độ dài bất kỳ (chỉ giới hạn bởi bộ nhớ RAM).

Cách Tối ưu xử lý chuỗi
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

// Hàm so sánh chuỗi số
bool cmp(string a, string b) {
    if (a.length() != b.length()) return a.length() < b.length();
    return a < b;
}

int main() {
    ifstream fin("TACHSO.INP");
    ofstream fout("TACHSO.OUT");

    string s;
    getline(fin, s);

    vector<string> numbers;
    string temp = "";
    bool inNumber = false;

    for (char c : s) {
        if (isdigit(c)) {
            temp += c;
            inNumber = true;
        } else {
            if (inNumber) {
                // Loại bỏ số 0 thừa
                size_t first_nonzero = temp.find_first_not_of('0');
                if (first_nonzero == string::npos) {
                    numbers.push_back("0");
                } else {
                    numbers.push_back(temp.substr(first_nonzero));
                }
                temp = "";
                inNumber = false;
            }
        }
    }

    if (inNumber) {
        size_t first_nonzero = temp.find_first_not_of('0');
        if (first_nonzero == string::npos) {
            numbers.push_back("0");
        } else {
            numbers.push_back(temp.substr(first_nonzero));
        }
    }

    // In thứ tự xuất hiện
    for (size_t i = 0; i < numbers.size(); ++i) {
        if (i > 0) fout << " ";
        fout << numbers[i];
    }
    fout << "\n";

    // Sắp xếp
    sort(numbers.begin(), numbers.end(), cmp);

    // In đã sắp xếp
    for (size_t i = 0; i < numbers.size(); ++i) {
        if (i > 0) fout << " ";
        fout << numbers[i];
    }

    return 0;
}
  • Time Complexity: O(N log N)
  • Space Complexity: O(N)

Đây là cách tiếp cận tổng hợp tốt nhất:

  1. Duyệt chuỗi để tách các cụm số.
  2. Sử dụng find_first_not_of('0') để loại bỏ các số 0 ở đầu một cách hiệu quả.
  3. Nếu chuỗi chỉ toàn '0', ta lưu "0".
  4. Sử dụng hàm so sánh tùy chỉnh (độ dài trước, nội dung sau) để sắp xếp.

Cách này đảm bảo độ chính xác như Solution 2 nhưng code gọn gàng và dễ đọc hơn.

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

Cách tiếp cận Time Space Tên
1 O(N log N) O(N) Xử lý chuỗi cơ bản với số nguyên
2 O(N * L log N) O(N * L) Xử lý chuỗi dạng số lớn (Big Integer)
3 O(N log N) O(N) Tối ưu xử lý chuỗi

Bài học kinh nghiệm

  • Vấn đề chính không chỉ là tách số mà là xử lý số 0 ở đầu (leading zeros). Ví dụ '001' và '1' là như nhau, nhưng '0' phải là '0'.
  • Sử dụng string thay vì long long là cách an toàn nhất để tránh tràn số khi xử lý các số lớn.
  • Quy tắc so sánh hai số lớn dạng chuỗi: So sánh độ dài trước, nếu bằng thì so sánh theo thứ tự từ điển.

Lỗi thường gặp

  • Quên xử lý trường hợp số toàn '0' (ví dụ '0000')导致 in ra chuỗi rỗng thay vì '0'.
  • Sử dụng atoi hoặc stoll trên chuỗi đầu vào chưa được loại bỏ số 0 đầu (mặc dù stoll tự xử lý, nhưng nếu dùng string sort thì phải xử lý thủ công).
  • Bỏ qua ký tự phân cách cuối cùng: Nếu chuỗi kết thúc bằng số, cần kiểm tra và thêm vào list sau vòng lặp.

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.