Tóm tắt đề bài

Cho một xâu \(s\) (độ dài \(\le 10^5\)) chỉ gồm chữ thường a…z và chữ số 0…9.

Yêu cầu:

• Tính tổng các chữ số xuất hiện trong xâu.
• In ra xâu đảo ngược của xâu đã cho nhưng bỏ hết các kí tự là chữ số. Nếu sau khi bỏ chữ số không còn kí tự nào thì in -1.

Phân tích

• Duyệt từng kí tự:
  • Nếu là chữ số: cộng vào tổng.
  • Nếu là chữ cái: đưa vào một danh sách/chuỗi để lát nữa đảo ngược.
• Độ dài tối đa \(10^5\) nên giải pháp tuyến tính \(O(n)\) là phù hợp.
• Lưu ý bẫy thường gặp:
  • Đọc input có thể là một dòng (không có khoảng trắng), chỉ cần cin >> s.
  • Tổng chữ số tối đa là \(9 \cdot 10^5 = 9 \times 10^5\), vẫn vừa int, nhưng dùng long long cho an toàn.

Hướng giải quyết

Nhận xét

• Xâu cần in ra ở dòng 2 thực chất là: lấy các chữ cái trong \(s\) theo thứ tự xuất hiện, rồi đảo ngược chuỗi đó.
• Có thể tạo chuỗi kết quả bằng cách duyệt từ phải sang trái và chỉ lấy chữ cái (không cần lưu riêng rồi đảo).

Thuật toán

1. Nhập xâu \(s\).
2. Khởi tạo sum = 0, chuỗi revLetters = "".
3. Duyệt từ trái sang phải để tính tổng chữ số:
   • Nếu s[i] là chữ số ('0' <= s[i] <= '9') thì sum += s[i] - '0'.
4. Duyệt từ phải sang trái để tạo xâu đảo ngược không chứa chữ số:
   • Nếu s[i] là chữ cái ('a' <= s[i] <= 'z') thì thêm vào revLetters.
5. In sum.
6. Nếu revLetters rỗng thì in -1, ngược lại in revLetters.

Độ phức tạp

• Thời gian: \(O(n)\) với \(n = |s|\) (duyệt 2 lần, vẫn tuyến tính)
• Bộ nhớ: \(O(n)\) cho chuỗi kết quả (trong trường hợp toàn chữ cái)

Code tham khảo

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

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

    string s;
    cin >> s;

    long long sum = 0;
    // Tính tổng các chữ số
    for (char c : s) {
        if ('0' <= c && c <= '9') sum += (c - '0');
    }

    // Tạo xâu đảo ngược nhưng bỏ chữ số
    string revLetters;
    revLetters.reserve(s.size());
    for (int i = (int)s.size() - 1; i >= 0; --i) {
        char c = s[i];
        if ('a' <= c && c <= 'z') revLetters.push_back(c);
    }

    cout << sum << "\n";
    if (revLetters.empty()) cout << -1 << "\n";
    else cout << revLetters << "\n";

    return 0;
}