Hiểu bài toán

Cho một xâu s có độ dài N bao gồm các ký tự 'a', 'b', và '?'. Các ký tự '?' có thể được thay thế bởi 'a' hoặc 'b'. Yêu cầu tìm cách thay thế các ký tự '?' sao cho giá trị của xâu sau khi thay thế là lớn nhất. Giá trị của một xâu được tính bằng tổng số cặp 'ab' trừ đi tổng số cặp 'ba' trong xâu đó (tức là duyệt từ đầu đến cuối, nếu gặp 'a' theo sau là 'b' thì cộng 1, nếu gặp 'b' theo sau là 'a' thì trừ 1).

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

Cách Quy hoạch động

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

#define int long long
const int N = 1e6 + 5;
int n;
string s;
int dp[N][3];

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

    cin >> n;
    cin >> s;
    s = " " + s;

    if(s[1] == 'a' || s[1] == '?')
        dp[1][1] = 0;
    else
        dp[1][1] = -1e18;

    if(s[1] == 'b' || s[1] == '?')
        dp[1][2] = 0;
    else
        dp[1][2] = -1e18;

    for(int i = 2 ; i <= n ; i++)
    {
        if(s[i] == 'a' || s[i] == '?')
            dp[i][1] = max(dp[i - 1][1] + 0,
                           dp[i - 1][2] - 1);
        else
            dp[i][1] = -1e18;

        if(s[i] == 'b' || s[i] == '?')
            dp[i][2] = max(dp[i - 1][1] + 1,
                           dp[i - 1][2] + 0);
        else
            dp[i][2] = -1e18;
    }

    cout << max(dp[n][1] , dp[n][2]);
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Đây là cách tiếp cận tổng quát nhất. Ta định nghĩa dp[i][0] là giá trị lớn nhất của xâu con từ 1 đến i với ký tự thứ i là 'a', và dp[i][1] là giá trị lớn nhất với ký tự thứ i là 'b'.

• Nếu s[i] = 'a' (hoặc '?' và ta chọn 'a'):
  • Nếu ký tự trước đó (i-1) là 'a': cặp 'aa' không cộng trừ gì. dp[i][0] = dp[i-1][0] + 0.
  • Nếu ký tự trước đó là 'b': cặp 'ba' bị trừ 1. dp[i][0] = dp[i-1][1] - 1.
  • Ta lấy giá trị lớn nhất của 2 trường hợp này.
• Nếu s[i] = 'b' (hoặc '?' và ta chọn 'b'):
  • Nếu ký tự trước đó là 'a': cặp 'ab' cộng 1. dp[i][1] = dp[i-1][0] + 1.
  • Nếu ký tự trước đó là 'b': cặp 'bb' không cộng trừ gì. dp[i][1] = dp[i-1][1] + 0.
  • Ta lấy giá trị lớn nhất của 2 trường hợp này. Nếu s[i] bị giới hạn (chỉ là 'a' hoặc chỉ là 'b'), ta chỉ cập nhật trạng thái tương ứng và đặt trạng thái còn lại về -vô cùng để loại trừ. Kết quả là max(dp[N]['a'], dp[N]['b']).

Cách Phân tích Tham lam (2 Trạng thái Cực đoan)

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

long long calc(string s) {
    long long res = 0;
    for (int i = 0; i + 1 < s.size(); i++) {
        if (s[i] == 'a' && s[i+1] == 'b') res++;
        else if (s[i] == 'b' && s[i+1] == 'a') res--;
    }
    return res;
}

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

    freopen("LONGXAU.INP","r",stdin);
    freopen("LONGXAU.OUT","w",stdout);

    int N;
    cin >> N;
    string s;
    cin >> s;

    string s1 = s, s2 = s;

    // TH1: thay tất cả '?' thành 'a'
    for(char &c: s1) if (c=='?') c='a';

    // TH2: thay tất cả '?' thành 'b'
    for(char &c: s2) if (c=='?') c='b';

    long long ans = max(calc(s1), calc(s2));
    cout << ans;
    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N) (do lưu xâu sao chép)

Giả sử ta thay thế tất cả '?' bằng 'a'. Khi đó xâu sẽ chỉ chứa 'a' và 'b'. Giá trị của xâu là tổng số 'ab' trừ đi tổng số 'ba'. Ta có thể tính giá trị này. Tương tự, nếu thay thế tất cả '?' bằng 'b', ta cũng có thể tính giá trị. Một nhận xét quan trọng: Nếu ta thay '?' bằng 'a', ta sẽ có nhiều 'a', nếu thay bằng 'b' ta có nhiều 'b'. Các xâu trung gian (kết hợp cả 'a' và 'b' cho '?') thường không tối ưu bằng 2 trường hợp cực đoan này. Ví dụ, nếu có một đoạn '?' ở giữa, việc để nó thành 'aaaa...a' hoặc 'bbbb...b' sẽ khác với 'abab...'. Tuy nhiên, lời giải này chỉ đúng trong một phạm vi nhất định của bài toán gốc (thường là biến thể 'dễ' hơn). Trong lời giải cụ thể này, người ta đã thử 2 trường hợp và chọn max. Có vẻ như dữ liệu bài toán hoặc logic bài toán ngầm cho phép điều này (hoặc bài toán có thêm ràng buộc khác không được ghi rõ).

Cách Tham lam Trực tiếp (Tối ưu hóa)

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

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

    freopen("LONGXAU.inp", "r", stdin);
    freopen("LONGXAU.out", "w", stdout);

    int N;
    cin >> N;
    string s;
    cin >> s;

    // Xây dựng xâu tối ưu
    for (int i = 0; i < N; i++) {
        if (s[i] == '?') {
            if (i > 0 && s[i - 1] == 'b') s[i] = 'b';
            else s[i] = 'a';
        }
    }

    long long ans = 0;
    for (int i = 0; i < N - 1; i++) {
        char a = s[i], b = s[i + 1];
        if (a == 'a' && b == 'b') ans += 1;
        else if (a == 'b' && b == 'a') ans -= 1;
    }

    cout << ans;
}

• Time Complexity: O(N)
• Space Complexity: O(1) (nếu sửa đổi xâu trực tiếp)

Lời giải này áp dụng một chiến lược tham lam cụ thể để lấp đầy dấu chấm hỏi:

• Nếu ký tự hiện tại là '?':
  • Nếu ký tự ngay trước nó là 'b', thì chọn 'b' (để tạo thành 'bb', không tăng/giảm giá trị, tránh tạo 'ba' bị trừ 1).
  • Ngược lại, chọn 'a' (để tạo 'aa' hoặc 'ab', tránh tạo 'ba'). Chiến lược này dựa trên việc tối ưu hóa cục bộ: tại mỗi bước, ta chọn giá trị giúp giá trị chuyển tiếp (transition) là tối ưu nhất có thể ngay tại thời điểm đó. Logic là cố gắng giữ cho các cặp ký tự 'ab' và 'ba' có lợi nhất. Đây là cách tiếp cận hiệu quả nhất về mặt thời gian và bộ nhớ.

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

Bài học kinh nghiệm

• Bài toán có thể được mô hình hóa bài toán quy hoạch động kinh điển: 'Tối ưu hóa giá trị xâu với ký tự bỏ trống'.
• Mặc dù DP giải quyết đúng bài toán, nhưng với các ràng buộc điển hình của Olympiad Tin học, các phương pháp tham lam (dựa trên tính chất đơn điệu của hàm số) hoặc quan sát các trường hợp biên (chỉ toàn a hoặc toàn b cho dấu ?) thường được sử dụng để giảm độ phức tạp.
• Giá trị của xâu thay đổi dựa trên các cặp ký tự kề nhau. Việc tối ưu hóa phụ thuộc vào việc chọn ký tự để tạo ra các cặp có lợi ('ab') và tránh các cặp có hại ('ba').

Lỗi thường gặp

• Lầm tưởng rằng chỉ cần thay tất cả '?' bằng 'a' hoặc 'b' là đủ cho mọi trường hợp (trừ khi bài toán có tính chất đặc biệt). Trong một số biến thể, việc xen kẽ 'a' và 'b' cho dãy '?' có thể tối ưu hơn.
• Bỏ qua việc xử lý các ký tự 'a' hoặc 'b' cố định sẵn trong xâu khi đưa ra quyết định thay thế '?'.
• Lỗi tràn số nếu dùng int thay vì long long cho tổng giá trị.