# Lời giải đề thi Tuyển sinh 10 trường Phổ thông Năng khiếu - năm 2025 - Môn Tin học

Chấm bài tại đây: [ClueOJ](https://oj.clue.edu.vn/contest/ptnk_ts10_25).

## Bài 1 - STREAK

### Tóm tắt đề bài

Cho dãy gồm $n$ xâu, mỗi xâu chỉ có dạng là `ONLINE` hoặc `OFFLINE` hoặc `IDLE`. Hãy tìm dãy các xâu **liên tiếp dài nhất**, mà các xâu trong đó đều là `ONLINE`.

Giới hạn: $n \le 1440$.

### Lời giải

Ta duy trì hai biến:
- $cur$ là độ dài của dãy con **kết thúc tại vị trí $i$ đang xét**, mà toàn bộ là xâu `ONLINE`. Dễ thấy, nếu xâu thứ $i$ không phải là `ONLINE`, thì $cur = 0$.
- $res$ là kết quả hiện tại.
Ta thực hiện thuật toán như sau: với mỗi xâu $i$:
- Nếu xâu thứ $i$ là `ONLINE`, đương nhiên $cur$ cộng thêm $1$, do ta có thêm một xâu.
- Ngược lại, $cur = 0$, vì dãy con liên tiếp hiện tại không còn toàn bộ là `ONLINE` nữa.
- Để tránh sai sót, dù vào trường hợp nào, ta đều cập nhật $res = max (res, cur)$.

Độ phức tạp: $O$ $(n)$.

## Bài 2 - EVTRIP

### Tóm tắt đề bài

Có một chiếc xe điện với dung lượng pin là $P$ đơn vị. Để di chuyển $1$ $km$ tốn $1$ đơn vị pin. Xe hết pin sẽ không thể di chuyển.
Có $N$ trạm sạc pin cho xe nằm tại các vị trí $a_1, a_2, ..., a_N$. Mỗi lần sạc thì pin sẽ về dung lượng tối đa là $P$ đơn vị.
Bạn sẽ bắt đầu ở vị trí $0$ $km$ với quả pin đầy. Hãy tìm cách di chuyển đến vị trí $D$ mà sạc ít lần nhất.

Giới hạn: $N \le 1000$, $P, D \le 10^9$, $a_i < D$.

### Lời giải
- Để tiện xử lý, ta sẽ sắp xếp các trạm sạc theo thứ tự tăng dần. Đồng thời, ta coi như $a_0 = 0$ vì ở vị trí $0$ pin đã đầy, nên ta coi vị trí $0$ cũng có trạm sạc.
- Ta sẽ quy hoạch động: gọi $dp[i]$ là **số lần sạc pin tối thiểu**, khi ta **có đầy pin ở vị trí $a_i$**, và **ta có sạc ở trạm $a_i$**.
- Để có thể đến trạm $a_i$ thì ta sẽ phải đầy pin ở một trạm $a_j$ với $j < i$ nào đó, mà $a_i - a_j \le P$.
- Vì vậy, ban đầu $dp[i] = \inf$, chỉ có $dp[0] = 0$. Ta có công thức truy hồi: $dp[i] = min (dp[j] + 1)$ với $0 \le j < i$ và $a_i - a_j \le P$.
- Kết quả sẽ là $min$ của các $dp[i]$ thỏa mãn $D - a[i] \le P$ để ta có đủ điện. Cần lưu ý trường hợp không cần sạc lần nào, đó là khi $D \le P$.

Độ phức tạp: $O$ $(N^2)$.

## Bài 3 - WORDGAME

### Tóm tắt đề bài

Cho một xâu $s$ chỉ gồm các ký tự in thường. Hãy loại bỏ ít ký tự nhất, mà sau khi loại bỏ xâu $s$ là xâu đối xứng.
Giới hạn: độ dài xâu $s \le 2000$.

### Lời giải

- Ta sẽ định nghĩa lại bài toán: Ta cần tìm xâu con dài nhất (có thể không cần liên tiếp) của xâu $s$, mà xâu đó là xâu đối xứng.
- Bài toán này có thể xử lý bằng quy hoạch động.
- Gọi $dp[i][j]$ là độ dài xâu con dài nhất trong xâu $s[i] \rightarrow s[j]$ mà xâu đó là xâu đối xứng
- Ta có công thức truy hồi:
- $dp[i][i] = 1$ với mọi $1 \le i \le n$.
- $dp[i][i + 1] = 2$ với mọi $1 \le i < n$ và $s_i = s{i + 1}$.
- $dp[i][j] = dp[i + 1][j - 1] + 2$ với $s_i = s_j$.
- $dp[i][j] = max (dp[i + 1][j], dp[i][j - 1])$ với $s_i \neq s_j$.
- Kết quả sẽ là $n - dp[1][n]$ do $dp[1][n]$ là độ dài xâu con dài nhất trong $s$ mà xâu đó là xâu đối xứng.

Độ phức tạp: $O$ $(n^2)$

## Bài 4 - BLOCKOPT

### Tóm tắt đề bài
Cho $n$ đồ vật, đồ vật thứ $i$ có giá trị là $f_i$ và giá mua là $s_i$, mỗi đồ vật chỉ có số lượng là $1$. Bạn có $m$ đồng để mua các đồ vật, và bạn cần mua các đồ vật sao cho tổng giá trị là lớn nhất, mà tổng giá mua $\le m$.

Tuy vậy, có $k$ ràng buộc dạng $(a, b)$ có nghĩa: nếu bạn mua vật $a$ thì phải mua vật $b$. $k$ ràng buộc này không tạo thành chu trình.

Giới hạn: $n \le 50$, $f_i, s_i, m \le 1000$.

### Lời giải
Bài toán này là bài toán thuộc NP-hard, vì vậy **không có lời giải chính xác trong thời gian đa thức.** Dưới đây chỉ là cách mình dựa vào để sinh test.

### Với $n \le 25$

Với giới hạn này, ta hoàn toàn có thể duyệt mọi tập con của $n$ phần tử. Sau đó, ta cần kiểm tra tập con này có thỏa mãn không.

Trước hết, ta cần kiểm tra tập con này có thỏa mãn $k$ điều kiện nói trên không. Có thể duyệt đủ $k$ điều kiện, tuy nhiên điều này là khá chậm. Ta có thể làm cách khác:
- Với mỗi điều kiện $i$, ta sẽ lưu các **vật phẩm phải mua** nếu mua vật phẩm thứ $i$ **dưới dạng bitmask.**
- Sau đó, ta có thể dễ dàng kiểm tra bằng phép toán AND hai tập hợp. Gọi $mask$ là tập con của $n$ phần tử ta đang thử, $must$ là tập các vật phẩm phải mua khi mua vật phẩm $i$ (mà vật phẩm $i$ cũng phải nằm trong $mask$), thì tập này thỏa mãn nếu $mask$ $\&$ $must = must$.

Sau đó, ta cần tính tổng số tiền phải trả cho tập con này, nếu $\le m$ thì ta cập nhật vào kết quả.

Độ phức tạp: $O$ $(2^n \times n)$, hằng số thấp do phép $\&$ khá nhanh.

Một số cách nhánh cận:
- Nếu tập ta đang duyệt, có tổng giá trị nhỏ hơn kết quả ta tìm thấy hiện tại, ta bỏ qua.
- Chỉ cần vi phạm một trong $k$ điều kiện, ta sẽ $break$ sớm.

### Với $n \le 50$

Đến đây có thể có một số cách như:
- Meet in the middle (độ phức tạp sẽ có dạng $2^x + 3^y$ với $x + y = n$). Ta sẽ chia $n$ thành hai tập $x$ và $y$ một cách tối ưu nhất.
- DP bitmask và lưu khéo các trạng thái.
- Tham lam, chẳng hạn theo tỷ lệ $\frac {f_i}{s_i}$.
- [Leo đồi (hill climbing)](https://en.wikipedia.org/wiki/Hill_climbing).
- [Luyện kim mô phỏng (simulated annealing)](https://en.wikipedia.org/wiki/Simulated_annealing), nâng cấp từ leo đồi.
- [Tối ưu cục bộ (local search)](https://en.wikipedia.org/wiki/Local_search_(optimization)).
- ~~if test~~.

Do điều kiện chỉ cần sinh test, mình đã để thời gian chạy cho mỗi test case từ $5 - 7$ phút để cho ra kết quả tối ưu nhất, đồng thời bỏ qua các test có thuật giải đúng.