Hiểu bài toán

Bài toán yêu cầu xử lý một chuỗi ký tự S. Nhiệm vụ gồm hai phần:

1. Đếm và in ra tổng số ký tự số (digits) có trong chuỗi S.
2. Tìm số nguyên tố lớn nhất được tạo thành từ các ký tự số liên tiếp nhau trong chuỗi S. Ví dụ: Chuỗi "abc123de45" chứa các số 123 và 45. Số lượng ký tự số là 5. Số nguyên tố lớn nhất trong hai số này là 123 (nếu 123 là số nguyên tố).

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

Cách Phân tích chuỗi và Kiểm tra Nguyên tố Tối ưu

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

bool isPrime(int n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen("ntmax.inp", "r", stdin);
    freopen("ntmax.out", "w", stdout);

    string s;
    cin >> s;

    int digit_count = 0;
    for (char c : s) {
        if (isdigit(c)) digit_count++;
    }
    cout << digit_count << "\n";

    int max_prime = 0;
    string current_num_str = "";

    // Thêm ký tự không phải số vào cuối để xử lý số cuối cùng dễ dàng
    s += '#'; 

    for (char c : s) {
        if (isdigit(c)) {
            current_num_str += c;
        } else {
            if (!current_num_str.empty()) {
                // Chuyển đổi sang số nguyên
                // Sử dụng long long để tránh tràn số nếu cần
                long long num = stoll(current_num_str);
                if (num > 0 && num <= INT_MAX && isPrime(num)) {
                    max_prime = max(max_prime, (int)num);
                }
                current_num_str = "";
            }
        }
    }

    cout << max_prime;
    return 0;
}

• Time Complexity: O(L * sqrt(Nmax)), với L là độ dài chuỗi, Nmax là giá trị số lớn nhất có thể (phụ thuộc độ dài chuỗi). Trong thực tế, với N <= 10^9, sqrt(N) ~ 31622.
• Space Complexity: O(L), lưu trữ chuỗi con hoặc O(1) nếu xử lý từng ký tự và dùng biến số.

Approach này đi theo 2 giai đoạn chính:

1. Đếm ký tự số: Duyệt qua chuỗi S một lần, tăng biến đếm mỗi khi gặp ký tự số. In ra kết quả.
2. Tìm số nguyên tố lớn nhất: Duyệt chuỗi S lần thứ hai để trích xuất các số nguyên.
   • Dùng một chuỗi tạm (hoặc biến số) để lưu các chữ số đang đọc được.
   • Khi gặp ký tự không phải số, kiểm tra số vừa đọc được.
   • Hàm isPrime được tối ưu hóa: loại bỏ các trường hợp chia hết cho 2, 3 ngay từ đầu; chỉ kiểm tra các ước từ 5 trở lên, bước nhảy 6 (i += 6) vì các số nguyên tố lớn hơn 3 đều có dạng 6k±1.
   • Cập nhật max_prime nếu số đó là nguyên tố và lớn hơn số hiện tại.
   • Xử lý trường hợp số nằm ở cuối chuỗi bằng cách thêm một ký tự rác vào cuối.

Cách Xử lý trực tiếp chuỗi không dùng STL

#include <iostream>
using namespace std;

bool checkPrime(int x) {
   if (x < 2) return false;
   if (x == 2 || x == 3) return true;
   if (x % 2 == 0) return false;
   for (int i = 3; i * i <= x; i += 2) {
      if (x % i == 0) return false;
   }
   return true;
}

int main() {
   ios::sync_with_stdio(false); cin.tie(NULL);
   freopen("ntmax.inp", "r", stdin);
   freopen("ntmax.out", "w", stdout);

   string s;
   cin >> s;

   int cntdigit = 0;
   int maxSNT = 0;
   int current_num = 0;

   // Duyệt chuỗi
   for (size_t i = 0; i < s.length(); i++) {
      if (isdigit(s[i])) {
         cntdigit++;
         // Xây dựng số hiện tại
         current_num = current_num * 10 + (s[i] - '0');
      } else {
         // Khi gặp ký tự раздел
         if (checkPrime(current_num)) {
            maxSNT = max(maxSNT, current_num);
         }
         current_num = 0;
      }
   }
   // Kiểm tra số cuối cùng
   if (checkPrime(current_num)) {
       maxSNT = max(maxSNT, current_num);
   }

   cout << cntdigit << "\n" << maxSNT;
   return 0;
}

• Time Complexity: O(L * sqrt(N))
• Space Complexity: O(L) (lưu chuỗi đầu vào) hoặc O(1) (không dùng thêm bộ nhớ lớn)

Đây là cách tiếp cận tối giản bộ nhớ.

1. Đếm số lượng: Dùng biến đếm cntdigit đếm trực tiếp trong vòng lặp.
2. Xây dựng số và kiểm tra: Dùng biến current_num để lưu số đang đọc.
   • Nếu gặp chữ số: current_num = current_num * 10 + digit.
   • Nếu gặp ký tự phân cách: Kiểm tra current_num có phải nguyên tố không, rồi reset current_num = 0.
   • Ưu điểm: Tránh việc tạo chuỗi con (substring) mới liên tục, tiết kiệm bộ nhớ và thời gian.
   • Hàm kiểm tra nguyên tố checkPrime sử dụng bước nhảy 2 (i += 2) để kiểm tra các ước lẻ.

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

Bài học kinh nghiệm

• Bài toán có thể được giải quyết bằng cách chia nhỏ thành 2 bài toán con: đếm ký tự và tìm max trên các đoạn con (số).
• Khi kiểm tra số nguyên tố, chỉ cần kiểm tra các ước từ căn bậc hai của nó. Tối ưu hơn bằng cách loại bỏ các số chia hết cho 2 và 3 trước, sau đó chỉ kiểm tra các ước dạng 6k±1.

Lỗi thường gặp

• Quên xử lý số nguyên tố nằm ở cuối chuỗi (vì không có ký tự phân cách phía sau). Cần gọi kiểm tra một lần nữa sau vòng lặp.
• Tràn số nguyên (Integer Overflow) khi đọc các số quá lớn từ chuỗi. Nên dùng long long khi lưu trữ số trong quá trình chuyển đổi.
• Hiệu suất: Nếu dùng stoi hoặc stoll trong vòng lặp để chuyển đổi chuỗi con, độ phức tạp có thể tăng lên. Việc dùng biến số num = num * 10 + digit là hiệu quả hơn.