**Lời giải đề thi chuyên Tin PTNK 2025-2026**
---
Tác giả: Hồ Bảo Phúc
> [!Note]
> Thông tin liên hệ tác giả: [**Hồ Bảo Phúc**](https://www.facebook.com/ho.bao.phuc.42906/)
---
> [!Warning]
> Lời giải chỉ mang tính chất tham khảo, không phải là lời giải chính thức.
> Các bạn có thể xem đề [**tại đây**](https://drive.google.com/drive/folders/1L55emJfISRcbxutPPdmF2hc8bH9Wr7Nm)
---
**Bài 1**
---
**Lời giải**
Đây là 1 bài kỹ thuật lập trình cơ bản, ta chỉ cần kiểm tra xem $a[i] == a[i - 1]$ và $a[i]$ == "ONLINE" thì ta cập nhật biến đếm và kết quả.
<details>
<summary><strong>Code</strong></summary>

/*
    author: hbphuc2009
    from: High School for the Gifted, VNU-HCM
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define nmax 100005
#define MOD 1000000007
#define endl '\n'

int n;
string a[nmax];
bool flag = false;

void input(){
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        if(a[i] == "ONLINE") flag = true;
    }
}

void solve(){
    if(flag == false){
        cout << 0;
        return;
    }
    int ans = 0;
    int d = 0;
    if(a[1] == "ONLINE") d ++, ans = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] == a[i - 1]){
            d ++;
        }
        else{
            if(a[i - 1] == "ONLINE") ans = max(ans, d);
            d = 1;
        }
    }

    if(a[n] == "ONLINE") ans = max(ans, d);
    cout << ans;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    freopen("STREAK.INP", "r", stdin);
    freopen("STREAK.OUT", "w", stdout);
    input();
    solve();
}

</details>

---
**Bài 2**
---
**Lời giải**
**Sort** lại các trạm sạc theo thứ tự tăng dần, nếu khoảng cách giữa 2 trạm sạc liền kề nhau (và khoảng cách giữa điểm đầu và trạm sạc 1, điểm đến và trạm sạc cuối) lớn hơn *p*, thì in ra -1.
Nếu $n = 0$ và *p* < $D$, in ra -1.
Duy trì biến *cur* là toạ độ của chiếc xe điện, ta chặt nhị phân xem có trạm sạc nào có toạ độ lớn hơn hoặc bằng *cur* + *p* hay ko, nếu bằng thì cập nhật *cur* tại trạm sạc đó, nếu lớn hơn thì cập nhật *cur* ở trạm sạc ngay trước đó và tăng biến đếm.

<details>
<summary><strong>Code</strong></summary>

    
/*
    author: hbphuc2009
    from: High School for the Gifted, VNU-HCM
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define nmax 1005
#define MOD 1000000007
#define endl '\n'

int n, p, target;
int a[nmax];

void input(){
    cin >> n >> p >> target;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
}

void solve(){
    sort(a + 1, a + n + 1);
    if((p < target - a[n]) or (n == 0 and p < target)){
        cout << -1 << endl;
        return;
    }
    for(int i = 1; i <= n; i++){
        if(a[i] - a[i - 1] > p){
            cout << -1 << endl;
            return;
        }
    }
    int sum = 0;
    int ans = 0;
    while(sum < target){
        if(sum + p >= target){
            break;
        }
        int k = lower_bound(a + 1, a + n + 1, sum + p) - a;
        if(a[k] == p){
            ans ++;
            sum = a[k];
        }
        else{
            ans ++;
            sum = a[k - 1];
        }
    }
    cout << ans << endl;
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    freopen("EVTRIP.INP", "r", stdin);
    freopen("EVTRIP.OUT", "w", stdout);
    input();
    solve();
}

</details>

---
**Bài 3**
---
**Lời giải**
Gọi `dp[i][j]` là số lần xoá ít nhất để xâu $s_i$ -> $s_j$ là xâu palindrome. Output là `dp[1][n]`
- `dp[i][j] = dp[i + 1][j - 1]` với `s[i] = s[j]`
- `dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]) + 1` với `s[i] != s[j]`
**Cơ sở**: `dp[i][i] = 0` , $1 <= i <= n$

<details>
<summary><strong>Code</strong></summary>

/*
    author: hbphuc2009
    from: High School for the Gifted, VNU-HCM
*/

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
#define nmax 2005
#define MOD 1000000007
#define endl '\n'

int n;
string s;
int dp[nmax][nmax];

void input(){
    getline(cin, s);
    n = s.size();
    s = " " + s;
}

void solve(){
    for(int i = 1; i <= n; i++) dp[i][i] = 0;
    for(int i = n - 1; i >= 1; i--){
        for(int j = i + 1; j <= n; j++){
            if(s[i] == s[j]){
                dp[i][j] = dp[i + 1][j - 1];
            }
            else{
                dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
    }
    cout << dp[1][n];
}

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    freopen("WORDGAME.INP", "r", stdin);
    freopen("WORDGAME.OUT", "w", stdout);
    input();
    solve();
}

</details>