# Solution #5: Đề thi TS10 trường PTNK - TP.HCM (2025-2026)
**Tác giả: Phan Thành Hưng (hungg_261)**

___

___

## Bài 1 (STREAK.*)

### Đề bài
Cho $T\ (T \le 1440)$ trạng thái hoạt động của người dùng, trong đó mỗi trạng thái mang giá trị "**ONLINE**", "**OFFLINE**" hoặc "**IDLE**". Hãy tìm độ dài của một đoạn trạng thái liên tiếp dài nhất mang giá trị "**ONLINE**".

**Input:**
- Dòng đầu chứa số nguyên dương $T$.
- $T$ dòng tiếp theo, mỗi dòng chứa một trong ba xâu kí tự "**ONLINE**", "**OFFLINE**" hoặc "**IDLE**" là trạng thái hoạt động của người dùng.

**Output:**
- Một số nguyên duy nhất là độ dài của đoạn trạng thái "**ONLINE**" dài nhất. Nếu không có đoạn "**ONLINE**" nào, in ra $0$.

**Sample test:**

**`STREAK.INP`**

5
ONLINE
ONLINE
OFFLINE
IDLE
ONLINE

**`STREAK.OUT`**

2

### Lời giải
Do bài này quá dễ nên mình quăng code lên luôn và không giải thích nhé (hoặc do mình lười kkk)
:::spoiler Code

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

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t;
    cin >> t;

    int ans = 0;
    int consecutive = 0;
    while(t--) {
        string state;
        cin >> state;

        if(state == "ONLINE") {
            ++consecutive;
        }
        else {
            ans = max(ans, consecutive);
            consecutive = 0;
        }
    }
    ans=max(ans, consecutive);

    cout<<ans<<'\n';
    return 0;
}

*Lưu ý:* Nhớ cập nhật biến `ans` thêm một lần nữa sau vòng lặp!

- **Độ phức tạp thời gian:** $O(T)$
- **Độ phức tạp không gian:** $O(1)$
:::

## Bài 2 (EVTRIP.*)
### Đề bài
Chiếc xe điện của bạn có lượng pin tối đa là $P_{max}$ đơn vị. Để di chuyển $1\ \text{km}$ tốn $1$ đơn vị pin. Xe sẽ không thể di chuyển nếu lượng pin còn lại không đủ để di chuyển tiếp. Có $N$ trạm sạc pin cho xe nằm tại các vị trí $D_1,D_2,...,D_N$. Mỗi lần sạc tại trạm thì lượng pin trong xe sẽ được nạp đầy trở lại thành $P$ đơn vị pin.
Biết rằng ban đầu bạn đang ở vị trí $0\ \text{(km)}$, hãy tìm cách di chuyển đến vị trí $D_{target}$ sao cho sử dụng ít lần sạc tại trạm nhất.

**Input:**
- Dòng đầu chứa 3 số nguyên $N,P_{max},D_{target}\ (0 \le N\le 1000, 1 \le P_{max} \le 10^9, 1 \le D_{target} \le 10^9)$.
- Dòng thứ $i$ trong $N$ dòng tiếp theo chứa số nguyên dương $a_i\ (D_i < D_{target})$ là vị trí của trạm sạc xe thứ $i$.

**Output:**
- Một số nguyên duy nhất là số lần sạc ít nhất để di chuyển từ $0$ tới $D$. Nếu không thể di chuyển, in ra $-1$.

**Sample test:**

**`EVTRIP.INP`**

3 175 350
80
180
280

**`EVTRIP.OUT`**

2

### Lời giải
Giả sử ta đang ở trạm sạc ở vị trí $D_i$, thì lúc này ta chắc chắn có đủ pin để di chuyển tới vị trí $D_i+P_{max}$. Do vậy nếu di chuyển được tới $D_i$ thì ta có thể di chuyển tới tất cả các vị trí trong đoạn $[D_i,D_i+P_{max}]$. Vậy ta đưa về bài toán cho $N$ đoạn $[L_i,R_i] (1 \le i \le N)$, tìm số đoạn cần chọn ít nhất để lấp đẩy một khoảng $[U,V]$ nào đó. Cụ thể hơn thì ta cần chọn ít nhất trong $N$ đoạn $[D_i,D_i+P_{max}]$ để lấp đầy đoạn $[0,D_{target}]$.

Để giải quyết bài toán này, ta sử dụng thuật toán tham lam. Giả sử ta đã lấp đầy được đoạn $[0,K]$. Ta cần nối thêm 1 đoạn nữa sao cho phần mở rộng ở bên phải là xa nhất (vì xa nhất nên sẽ có nhiều "cơ hội" nối được thêm với các đoạn khác và tiến gần $D_{target}$ hơn). Vậy ta tìm cách nối thêm 1 đoạn $[L,R]$ nữa sao cho $[L,R]$ giao nhau với $[0,K]$ và $R$ lớn nhất. Để 2 đoạn $[a,b]$ và $[c,d]$ giao nhau thì $\max(a,c) \le \min(b,d)$.
:::info
**Chứng minh:**
> Để 2 đoạn $[a,b]$ và $[c,d]\ (a \le b, c \le d)$ giao nhau thì $\max(a,c) \le \min(b,d)$.

Gọi $w_1,w_2$ lần lượt là độ dài của 2 đoạn, không mất tỉnh tổng quát, chẳng hạn $w_1 = b-a, w_2=d-c$.
Khi kết hợp 2 đoạn đó, tất cả các phần được phủ nằm trong đoạn $[\min(a,c),\max(b,d)]$. Nếu chúng giao nhau, chứng tỏ một phần (phần giao) đã được gộp lại thành chung của cả hai đoạn $\Rightarrow$ độ dài thực tế của đoạn mới sẽ ít hơn tổng độ dài của cả 2 đoạn, cụ thể là $\max(b,d)-\min(a,c) \le w_1+w_2$. Ta có:
$$ \max(b,d)-\min(a,c) \le w_1+w_2 $$ $$ \max(b,d)-\min(a,c) \le (b - a) + (d - c) $$ $$ \max(b,d)-\min(a,c) \le (b+d)-(a+c) $$ $$ (a+c)-\min(a,c) \le (b+d)-\max(b,d) $$ mà $\min(u,v)+\max(u,v)=u+v$ nên
$$\max(a,c) \le \min(b,d)$$

> Hình minh họa:
> 
> **Lưu ý:** trong hình minh hoạ điều kiện 2 đoạn giao nhau khác rỗng nên nếu dấu bằng xảy ra thì theo như hình là không giao nhau. Tuy nhiên về ý tưởng thì cũng giống nhau.
> *Nguồn: https://stackoverflow.com/a/25369187*

:::

$\Rightarrow$ với $K$ thì ta sẽ tìm tất cả các đoạn $[L_i,R_i]$ sao cho $L_i \le K$ và lấy max của mọi $R_i$. Sử dụng kĩ thuật **hai con trỏ**, ta sắp xếp lại các đoạn tăng dần theo $L_i$. Sau đó, với mỗi $K$, ta duyệt qua tất cả các đoạn $[L_j,R_j]$ thỏa $L_j \le K$ bằng con trỏ thứ hai, và cập nhật lại $K$ thành max của mọi $R_j$ thỏa $L_j \le K$. Do ban đầu xe đang ở vị trí $0$ và có đầy pin nên nó có thể di chuyển tới vị trí $P_{max}$ mà không cần chọn đoạn nào, vậy ban đầu $K=P_{max}$. Nếu $K \ge D_{target}$ thì ta không cần chạy nữa do đã di chuyển tới được $D_{target}$, còn nếu sau khi lặp hết mà $K < D_{target}$ thì ta trả ra $-1$ do dù có đi xa nhất cũng không tới được $D_{target}$.

:::spoiler Code

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

const int MAXN = 1000;
struct interval{
    int L, R;
} D[MAXN + 5];

bool cmp(interval& u, interval& v){
    return u.L < v.L;
}

void solve(int N, int P_max, int D_target){
    // sắp xếp lại theo L tăng dần nhằm thực hiện hai con trỏ
    sort(D + 1, D + N + 1, cmp);
    
    int covered = P_max; // covered chính là K -> đã phủ được đoạn [0, K]
    int ans = 0;
    for(int i = 1; i <= N;){
        // nếu ta phủ qua D_target, nghĩa là ta đã đến được đó => không cần chọn tiếp nữa
        if(covered >= D_target){
            break;
        }
        
        int furthest = covered;
        // ta cập nhật max của R_j với tất cả L_j <= K, do L_j đã sắp xếp nên ta chỉ cần duyệt tiếp
        // ở khúc này có thể coi là đang có một con trỏ j đi nhanh hơn i -> kĩ thuật hai con trỏ
        while(i <= N && D[i].L <= covered){
            furthest = max(furthest, D[i].R);
            ++i;
        }
        
        // nếu covered == furthest, chứng tỏ không có cập nhật max nào cả => ko có đoạn nào giao với [0,K]
        // do vậy dù có làm gì thì ta không nối tiếp được và kéo dài K thêm => trả ra -1
        if(covered == furthest){
            cout << "-1\n";
            return;
        }
        
        // cập nhật lại đoạn phủ mới
        covered = furthest;
        
        ++ans;
    }
    
    // nếu đã đi qua hết tất cả các đoạn rồi mà vẫn chưa phủ tới D_target => trả ra -1
    if(covered < D_target){
        cout << "-1\n";
        return;
    }
    
    cout << ans << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int N, P_max, D_target;
    cin >> N >> P_max >> D_target;
    for(int i = 1; i <= N; ++i){
        int Di;
        cin >> Di;
        
        // [L_i, R_i] = [D_i, D_i + P_max]
        D[i] = {Di, Di + P_max};
    }
    
    solve(N, P_max, D_target);
    return 0;
}

- **Độ phức tạp thời gian:** $O(N \log N + N)$
- **Độ phức tạp không gian:** $O(N)$
:::

## Bài 3 (WORDGAME.*)
### Đề bài
Cho một xâu $s$ chỉ gồm các kí tự tiếng Anh in thường. Bạn được phép xóa một vài kí tự bất kì ra khỏi xâu (bạn cũng có thể chọn không xóa kí tự nào) sao cho xâu còn lại sau khi xóa là một xâu palindrome và độ dài của xâu đó là dài nhất.

**Input:**
- Một dòng là xâu $s\ (|s| \le 2000)$ gồm các kí tự tiếng Anh in thường.

**Output:**
- Một số nguyên duy nhất là số kí tự tối thiểu cần xóa.

**Sample test:**

**`WORDGAME.INP`**

abcca

**`WORDGAME.OUT`**

1

### Lời giải
Như đề đã nói, ta cần xóa một vài kí tự để xâu còn lại là **xâu palindrome dài nhất**. Vậy số kí tự cần xóa sẽ là độ dài của xâu trừ đi độ dài của xâu con palindrome dài nhất. Do ta được phép xóa các kí tự bất kì nên xâu con này không nhất thiết phải bao gồm các kí tự liên tiếp trong xâu $s$. Cụ thể hơn, gọi xâu palindrome đó là xâu $p$ thì số kí tự tối thiểu cần xóa là $|s| - |p|$. Vậy vấn đề ở đây là tìm xâu palindrome dài nhất từ xâu $s$.
Ta có thể nhận thấy tính chất con tối ưu trong bài toán tìm xâu con palindrome dài nhất. Giả sử ta có một xâu $p$ là palindrome, nếu ta loại bỏ kí tự ở đầu và ở cuối xâu $p$ cùng một lúc, thì ta sẽ còn lại một xâu mới, cũng là palindrome nốt. Vậy ta đã tìm ra được cấu trúc con ở trong bài toán này.
Gọi $dp[i][j]$ là độ dài xâu palindrome (không nhất thiết liên tiếp) dài nhất trong một đoạn con liên tiếp từ $i$ tới $j$.
- Nếu $s_i = s_j$
Với một xâu palindrome dài nhất trong đoạn từ $i+1$ tới $j-1$, ta có thể thêm 2 kí tự bằng nhau $s_i$ vào đầu và $s_j$ vào cuối xâu đó để được xâu palindrome mới có độ dài thêm 2 đơn vị.
Do vậy, $dp[i][j] = dp[i+1][j-1] + 2$

- Nếu $s_i \neq s_j$
Do $s_i$ khác $s_j$, độ dài của xâu palindrome dài nhất không thay đổi. Một xâu con trong đoạn $i$ tới $j$ có thể được mở rộng từ xâu con trong đoạn từ $i$ tới $j-1$ hoặc từ $i+1$ tới $j$. Ta sẽ lấy giá trị lớn nhất giữa 2 xâu con đấy.
Do vậy, $dp[i][j] = \max(dp[i][j-1],dp[i+1][j])$

Đối với trường hợp cơ sở, ta có $dp[i][i] = 1$ do một đoạn liên tiếp từ $i$ tới $i$ chỉ có đúng một kí tự, và $s_i$ là xâu palindrome.

Tổng kết lại từ các trường hợp trên, ta có công thức truy hồi sau:
$$
dp[i][j] =
\begin{cases}
1, & \mbox{if } i=j \\
dp[i+1][j-1]+2, & \mbox{if } s_i = s_j \\
\max(dp[i+1][j], dp[i][j-1]), & \mbox{if } s_i \neq s_j
\end{cases}
$$

Vậy, kết quả của bài toán chính là $n - dp[1][n]$ với $n$ là độ dài xâu $s$.

Vì để tính được $dp[i][j]$ cần phải tính được luôn cả $dp[i+1][j-1]$, $dp[i+1][j]$ và $dp[i][j-1]$. Điểm chung của chúng là đều có độ dài nhỏ hơn đoạn từ $i$ tới $j$. Vậy ta chạy 2 vòng lặp lồng nhau để duyệt theo độ dài tăng dần, và với mỗi độ dài ta duyệt $i$ và tìm được $j\ (j = i + \text{len} - 1)$.

:::spoiler Code

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

const int MAXN = 2000;
int dp[MAXN + 5][MAXN + 5];

void solve(const string& s, int n){
    for(int i = 1; i <= n; ++i){
        dp[i][i] = 1;
    }
    
    for(int len = 2; len <= n; ++len){
        for(int i = 1; i + len - 1 <= n; ++i){
            int j = i + len - 1;
            
            if(s[i] == s[j]){
                dp[i][j] = dp[i + 1][j - 1] + 2;
            }
            else{
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
            }
        }
    }
    
    cout << n - dp[1][n] << '\n';
}

signed main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    string s;
    cin >> s;
    
    int n = s.size();
    
    // chuyển từ 0-indexed sang 1-indexed để cho thuận tiện
    s = '#' + s;
    solve(s, n);
    return 0;
}

- **Độ phức tạp thời gian:** $O(|s|^2)$
- **Độ phức tạp không gian:** $O(|s|^2)$
:::

## Bài 4 (BLOCKOPT.*)
### Lời giải
:::danger
Bài này sẽ không được viết lời giải do đang xuất hiện nhiều tranh cãi về tính khả thi của bài này.
:::