Hiểu bài toán

Cho một xâu ký tự S chỉ gồm các ký tự 'C' (Correct) và 'N' (No Correct). Điểm số được tính như sau: Với mỗi ký tự 'N', điểm là 0. Với mỗi ký tự 'C' ở vị trí i, điểm nhận được bằng số lượng 'C' liên tiếp tính từ vị trí đó trở về trước (bao gồm chính nó). Ví dụ: Chuỗi 'CC' có điểm là 1 (tại vị trí 1) + 2 (tại vị trí 2) = 3. Yêu cầu tính tổng điểm của toàn bộ xâu.

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

Cách Duyệt tuần tự (Sliding Window)

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

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

    string s;
    cin >> s;

    long long total = 0;
    long long cnt = 0;

    for (char c : s) {
        if (c == 'C') {
            cnt++;
            total += cnt;
        } else { 
            cnt = 0;
        }
    }

    cout << total;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Đây là cách tiếp cận trực quan nhất. Ta duyệt qua từng ký tự của xâu, duy trì một biến đếm cnt để lưu số lượng 'C' liên tiếp hiện tại. Nếu gặp 'C', ta tăng cnt lên 1 và cộng giá trị của cnt vào tổng điểm. Nếu gặp 'N', ta đặt lại cnt về 0 vì chuỗi 'C' liên tiếp bị đứt đoạn. Độ phức tạp thời gian là O(n) do chỉ duyệt qua xâu một lần, và bộ nhớ là O(1) vì chỉ cần lưu vài biến.

Cách Duyệt tuần tự với biến đếm

#include <iostream>
using namespace std;

int main()
{
    string s;
    cin >> s;
    int diem = 0, d = 0;
    for(size_t i = 0; i < s.size(); i++)
    {
        if(s[i] == 'N')
        {
            d = 0;
        }
        else
        {
            d++;
            diem = diem + d;
        }
    }
    cout << diem;
    return 0;
}

• Time Complexity: O(n)
• Space Complexity: O(1)

Cách giải quyết này về bản chất giống với cách đầu tiên. Biến d giữ vai trò là biến đếm số lượng 'C' liên tiếp. Logic xử lý hoàn toàn tương tự: reset về 0 khi gặp 'N' và tăng dần khi gặp 'C'. Việc sử dụng int cho biến điểm và đếm có thể gây tràn số nếu xâu đầu vào quá dài (n > 10^5), do đó giải pháp sử dụng long long (Solution 1) là an toàn hơn.

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

Bài học kinh nghiệm

• Vấn đề có thể được giảm xuống bài toán đếm độ dài các đoạn 'C' liên tiếp. Nếu độ dài đoạn 'C' là k, tổng điểm đóng góp bởi đoạn này là 1 + 2 + ... + k = k*(k+1)/2.
• Cách tiếp cận trực tiếp bằng cách duy trì biến đếm (running count) là hiệu quả nhất về cả thời gian và bộ nhớ, không cần lưu trữ thêm dữ liệu phức tạp.

Lỗi thường gặp

• Sử dụng biến đếm và biến tổng có kiểu dữ liệu nhỏ (như int) có thể gây tràn số (integer overflow) nếu xâu đầu vào dài và có nhiều 'C' liên tiếp. Nên dùng kiểu long long.
• Làm sai quy luật tính điểm: Ví dụ, nhầm lẫn giữa số lượng 'C' liên tiếp và chỉ số của 'C'. Với đoạn 'CCC', điểm số phải là 1+2+3 = 6, không phải 3+3+3.