# Lời giải đề thi Tuyển sinh 10 tỉnh Vĩnh Phúc - năm 2025 - môn Tin học

Tác giả: [noodles0428](https://oj.clue.edu.vn/user/noodles0428) + [duong3982](https://oj.clue.edu.vn/user/duong3982)

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

## Bài 1 - Quà

> Tác giả: [noodles0428](https://oj.clue.edu.vn/user/noodles0428).

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

Cho $3$ số nguyên dương $a, b, c$ và số nguyên $k$. Tính tổng các số cần thêm vào mỗi số $a, b, c$ sao cho không có số nào có giá trị $< k$.

### Lời giải

Rõ ràng, nếu $x \ge k$ (với $x$ là $a$ hoặc $b$ hoặc $c$) thì ta không cần thêm bất cứ đơn vị nào vào $x$. Ngược lại, ta cần thêm $k - x$ để $x = k$.

Do đó, kết quả bài toán chính là: $max(0, k - a) + max(0, k - b) + max(0, k - c)$.

ĐPT: $O$($1$)

## Bài 2 - Tàu điện

> Tác giả: [noodles0428](https://oj.clue.edu.vn/user/noodles0428).

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

Gần nhà Bờm có ga tàu điện. Số hiệu chuyến tàu $x$ sẽ dừng ở $T_0 + x \times D$. Có $N$ hành khách chờ tàu, hành khách thứ $i$ chờ ở thời điểm $s_i$ và sẽ lên chuyến đầu tiên không sớm hơn $s_i$. Hãy xác định số hiệu chuyến tàu của từng hành khách sẽ lên.

### Lời giải

Với mỗi khách, ta cần tìm số nguyên $x$ nhỏ nhất sao cho $T_0 + k \times D \le s_i$. Tức là $k = \frac{s_i - T_0 + D - 1}{D}$.

Nhưng do $k$ đánh số từ $1$, nên số hiệu chuyến tàu sẽ là $k + 1$

ĐPT: $O$($n$).

## Bài 3 - Trò chơi

> Tác giả: [noodles0428](https://oj.clue.edu.vn/user/noodles0428).

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

Cho một dãy số $a$ biểu đạt giá trị của các đồ chơi, là hoán vị từ 1 đến $2 \times N$. Đồ chơi của Bờm có giá trị từ $a_1$ đến $a_N$, đồ chơi của cuội có các giá trị còn lại.

Luật chơi như sau:
- Hai người lần lượt chọn món đồ từng ván, mỗi người chỉ dùng món đồ chơi đúng 1 lần.
- Người có đồ chơi có giá trị lớn hơn thì thắng.

Hỏi trong trường hợp may mắn nhất, hay trường hợp Cuội không biết chơi và Bờm có thể can thiệp toàn bộ, Bờm có thể thắng được bao nhiêu ván?

### Subtask 1. $n \le 100$

> Subtask này chỉ với mục đích chứng minh tính đúng đắn của thuật tham lam trong subtask 2, và có thể sử dụng nhiều kiến thức ngoài phạm vi của kỳ thi Tuyển sinh 10.

Gọi $B = {b_1, b_2, ..., b_N}$ là danh sách đồ chơi của Bờm.

Gọi $C = {c_1, c_2, ..., c_N}$ là danh sách đồ chơi của Cuội.

Ta dựng đồ thị hai phía, với đỉnh thứ $i$ của Bờm nối với đỉnh thứ $j$ của Cuội khi $b_i > c_j$. Điều này có nghĩa, đỉnh $i$ của Bờm nối với đỉnh $j$ của Cuội nếu đồ chơi thứ $i$ của Bờm có thể thắng đồ chơi thứ $j$ của Cuội.

Có thể thấy, ta cần tìm [cặp ghép cực đại](https://wiki.vnoi.info/algo/graph-theory/max-matching) trên đồ thị hai phía này, và đó cũng là kết quả.

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

### Subtask 2. $n \le 50000$

Gọi $B = {b_1, b_2, ..., b_N}$ là danh sách đồ chơi của Bờm đã được sắp xếp tăng dần.

Gọi $C = {c_1, c_2, ..., c_N}$ là danh sách đồ chơi của Cuội đã được sắp xếp tăng dần.

Ta lưu $i$ là chỉ số hiện tại của Bờm, và $j$ là chỉ số hiện tại của Cuội. Với mỗi $j$, ta tìm $i$ nhỏ nhất sao cho $a_i > b_j$, sau đó ghép cặp. Với các phần tử $j$ mà ta không tìm ra $i$ thỏa mãn nữa, ta sẽ chấp nhận Bờm thua.

Có thể chứng minh đây luôn là cách làm tối ưu.

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

:::spoiler Chứng minh
Gọi $M$ là cặp ghép cực đại như trong thuật toán ở subtask 1. Gọi $K = |M|$. Giả sử trong cặp ghép cực đại này ta có các bộ ta chọn là ($b_{i_1}, c_{j_1}$), ($b_{i_2}, c_{j_2}$), ..., ($b_{i_k}, c_{j_k}$). và $b_{i_x} > c_{i_x}$.

Xét $b_1$ và $c_1$.
#### Trường hợp 1. $b_1 > c_1$.
- Nếu $b_1 > c_1$, thì thuật toán tham lam sẽ ghép ($b_1, c_1$).
- Trong cặp ghép cực đại $M$ nói trên, có ba khả năng:
- Trường hợp 1. Cặp ghép đó đã ghép $c_1$ với $b_x$ nào đó nhưng $x > 1$. Vì $b_1 < b_x$, nên ta có thể đổi cặp ($b_x, c_1$) thành $(b_1, c_1)$ mà không làm mất tính hợp lệ hay giảm tính tối ưu của kết quả.
- Trường hợp 2. Cặp ghép đó không ghép $c_1$ với bất kỳ $b_x$ nào. Với trường hợp này, ta có thể sửa $M$: thay đổi một cặp $c_{j_t}$ nào đó với $t > 1$ để đưa $c_1$ ghép với $b_1$. Như vậy, kể cả $M$ không dùng $b_1$ thì ta vẫn tạo ra một cặp ghép cực đại mới với cùng kích thước, mà lại có cặp ($b_1, c_1$).
- Trường hợp 3. Cặp ghép đó đã ghép $b_1$ với $c_1$. Trường hợp này không bình luận gì thêm.
- Vì vậy, ta xóa $b_1$ và $c_1$ khỏi hai dãy, chuyển về bài toán con với $2n - 2$ món đồ chơi. Theo nguyên lý quy nạp toán học, ta chứng minh được thuật toán tham lam của ta đã đúng.

#### Trường hợp 2. $b_1 < c_1$.
- Thuật toán tham lam sẽ bỏ $b_1$.
- Trong mọi bộ ghép hợp lệ, chắc chắn không có bộ ghép nào dùng $b_1$, vì $b_1 < c_1 < c_j$.
- Như vậy, ta có thể loại hẳn $b_1$ và $c_n$. mà không làm giảm kích thước cặp ghép cực đại tối đa. $M$ sẽ chỉ dùng các món đồ từ $2$ tới $n$ của Bờm. Bài toán tiếp tục với $n - 1$ món đồ mỗi người của Bờm và Cuội.
- Theo nguyên lý quy nạp toán học, ta chứng minh được thuật toán tham lam của ta đã đúng.
:::

## Bài 4 - Chọn

> Tác giả: [duong3982](https://oj.clue.edu.vn/user/duong3982)

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

Cho mảng $a$ gồm $n$ phần tử dương. Với mọi $x$ ($1 \le x \le \lfloor \frac {n + 1}{2} \rfloor$), ta cần chọn ra $x$ phần tử sao cho tổng $x$ phần tử đó là lớn nhất. Tuy nhiên ta không được chọn hai phần tử liên tiếp trong dãy gốc.

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

### Subtask 1. $n \le 20$

Duyệt nhị phân mọi cách chọn.

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

### Subtask 2. $n \le 2000$, các phần tử là bằng nhau

Ta luôn có thể chọn ra $k$ phần tử không kề nhau, và mọi cách chọn đều có tổng bằng nhau. Đáp án cho truy vấn thứ $i$ sẽ là $a_1 \times i$.

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

### Subtask 3. $n \le 2000$

Ta sẽ quy hoạch động.

Gọi $dp[i][j]$ là tổng lớn nhất khi **xét $i$ phần tử đầu tiên**, **phần tử cuối cùng ta chọn là phần tử $i$**, và ta đã chọn tổng $j$ phần tử.

Ta có công thức truy hồi:
- $dp[i][1] = a[i]$ (cơ sở).
- $dp[i][j] = max (dp[k][j - 1])$ với $1 \le k \le i - 2$ để đảm bảo không chọn hai phần tử kề nhau.

Để xử lý công thức này, ta sử dụng prefix max.

Kết quả với truy vấn thứ $i$ là $max$ của các $dp[x][i]$ với $1 \le x \le n$.

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

### Subtask 4. $n \le 200000$

Nhận xét 1: Tập nghiệm của bài toán có dạng xâu nhị phân, tương ứng việc phần tử thứ $i$ được chọn hay không.

Nhận xét 2: Khi ta cần tính kết quả với số phần tử $x + 1$, mà ta đã biết kết quả của $x$, ta có hai cách:
- Cách 1: Ta sẽ chọn thêm một phần tử trong tập ứng cử, mà không kề với bất kỳ phần tử nào ta đã chọn.
- Cách 2: Ta bỏ một phần tử ta đã chọn đi, sau đó ta cần chọn bù lại hai phần tử. **Có thể chứng minh, ta luôn luôn chọn hai phần tử kề với phần tử ta vừa bỏ đi.** Với cách chọn này, số phần tử tăng thêm là $-1 + 2 = 1$, đúng như ta muốn.

::: spoiler Chứng minh
Ta sẽ chứng minh việc ta bỏ đi một phần tử $i$, sau đó chỉ chọn một trong hai phần tử $i - 1$ và $i + 1$ là chưa tối ưu.

Nếu ta chỉ lựa chọn một trong hai phần tử $i - 1$ hoặc $i + 1$, thì sẽ tồn tại một phần tử $j$ khác mà ta sẽ chọn cùng. Lúc này, ta hoàn toàn đã chọn phần tử $j$, và một trong hai phần tử $i - 1$ hoặc $i + 1$ ở truy vấn thứ $x$ ngay trước truy vấn ta đang xét. Chắc chắn trong cách chọn ở truy vấn thứ $x$ ngay trước truy vấn ta đang xét, chọn phần tử thứ $i$ sẽ không là cách tối ưu.
:::

Vì vậy, ta sẽ duy trì $b_i$ là hiệu quả của việc đổi trạng thái của phần tử thứ $i$. Việc đổi trạng thái này sẽ có nghĩa: bỏ đi nếu ta đang chọn phần tử $i$, chọn thêm nếu ta chưa chọn.

Ban đầu, $b_i = a_i$ toàn bộ, do toàn bộ các phần tử đều chưa được chọn.

Ta sẽ lặp từ $1$ tới $\lfloor \frac {n + 1}{2} \rfloor$, với mỗi bước ta cần làm như sau:
- Đầu tiên, chọn ra chỉ số $i$ là chỉ số có giá trị $b_i$ lớn nhất. Kết quả sẽ cộng thêm $b_i$. Sau đó ta cần cập nhật lại các giá trị của tập ứng cử này.
- $b_i$ sẽ được cập nhật thành $-b_i + b_{i - 1} + b_{i + 1}$, như chứng minh ở trên, khi ta chuyển $i$ thành không chọn, ta sẽ luôn chọn hai phần tử kề với nó.
- Tập ứng cử cần được xóa $i - 1$ và $i + 1$, do nếu ta cần chọn $i - 1$ hoặc $i + 1$, ta sẽ chỉ cần thực hiện "thay đổi" tập nghiệm ở vị trí $i$ như đã nói ở trên.

Vấn đề đặt ra là quản lý tập ứng cử này, thay vì duyệt từ $1$ tới $n$ để tìm max. Để xử lý thao tác thêm và xóa một cách hợp lý, ta có thể sử dụng cấu trúc dữ liệu `set` trong C++.

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

> Bạn đọc nên thử cài đặt theo hướng lặp để tìm phần tử tốt nhất, trước khi nâng cấp lên áp dụng set.