# Lời giải đề thi thử Tuyển sinh 10 trường THPT chuyên Khoa học Tự nhiên - Môn Tin học

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

## Bài 1: BIG3

Tóm tắt đề bài: Nhập vào $n$ ($1 \le n \le 10^7$) số nguyên dương. Hãy in ra số lớn thứ $3$ trong mảng.

### Subtask 1: $n \le 10^5$.

Sắp xếp lại mảng và in ra phần tử thứ $3$.

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

### Subtask 2: $n \le 10^7$.

Duy trì ba biến $a$, $b$, $c$ tương ứng phần tử lớn nhất, lớn nhì và lớn ba. Ban đầu, cả ba số đều bằng $0$.

Nhập liên tục vào $n$ số $x$, xét các trường hợp sau:
- Nếu $x \ge a$, ta thấy: số lớn nhất sẽ trở thành số thứ hai, số lớn thứ hai trở thành số lớn thứ ba. Vì vậy, $c = b$, $b = a$, và $a = x$.
- Nếu $x \ge b$, tương tự như trên, ta sẽ có $c = b$, $b = x$.
- Nếu $x \ge c$, ta sẽ có $c = x$.
- Cuối cùng, ta bỏ qua số $x$ vì số $x$ sẽ không đóng góp vào kết quả.

Cuối cùng, ta in ra $c$, hay số lớn thứ ba.

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

> Cách này có thể AC với time limit 2 giây. Để tối ưu hơn nữa, có thể sử dụng [fast input](https://codeforces.com/blog/entry/120183), tuy nhiên điều này là không tưởng trong một kỳ thi offline.

## Bài 2: EQUA3

Tóm tắt đề bài: Cho phương trình $ax^3 + bx^2 + cx + d = 0$, với $a, b, c, d$ là các số nguyên dương và $\le 1000$. Tìm một nghiệm bất kỳ của phương trình này.

Có thể chứng minh phương trình này luôn có nghiệm **âm.** Một nghiệm dương sẽ dẫn tới vô lý, vì cả phương trình sẽ lớn hơn $0$.

Gọi $f (x) = ax^3 + bx^2 + cx + d$.

Xét đạo hàm $f' (x) = 3ax^2 + 2bx + c$. Xét $\triangle = (2b)^2 - 4 \times 3a \times c = 4b^2 - 12ac$.

Nếu $\triangle \le 0$, thì $f(x)$ sẽ đồng biến trên $R$. Vì vậy, ta có thể tìm kiếm nhị phân để tìm ra nghiệm.

Ngược lại, $f'(x)$ sẽ có hai nghiệm $x_1, x_2$ với $x_1 < x_2$. Theo tính chất tam thức bậc hai, ta có $f'(x) < 0$ với mọi $x_1 < x < x_2$, hay $f(x)$ nghịch biến trên $(x_1, x_2)$. Ngược lại, $f(x)$ sẽ đồng biến trên $(-\infty, x_1]$ và $[x_2, \infty)$. Từ đó, ta có thể chia ba trường hợp và tìm kiếm nhị phân.

Vì sai số cho phép bài này rất nhỏ ($10^{-9}$), nên ta sẽ cần chia đôi miền nghiệm khoảng $10^6$ lần.

Độ phức tạp: $O$ ($10^6$).

## Bài 3: REC3

Tóm tắt đề bài: Cho bảng kích thước $N \times M$, và $K$ ô có chữ $X$. Hãy đếm số lượng hình chữ nhật con có ít nhất một chữ $X$.

### Subtask 1: $K = 1$

Ở subtask này, vì chỉ có một chữ $X$, ta cần tìm số hình chữ nhật con chứa ô $(x_1, y_1)$.

Dễ thấy: Một hình chữ nhật con có ô trên trái $(x, y)$ và ô dưới phải $(u, v)$ sẽ thỏa mãn nếu: $x \le x_1 \le u$ và $y \le y_1 \le v$.

Vì vậy, chọn ra $x$ có $x_1$ cách chọn, chọn ra $y$ có $y_1$ cách chọn, chọn ra $u$ có $n - x_1 + 1$ cách chọn, chọn ra $v$ có $m - y_1 + 1$ cách chọn. Ta nhân các số này lại và nhận được kết quả.

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

### Subtask 2: $K = 2$

Vẽ sơ đồ Venn, ta thấy: kết quả là số lượng hình chữ nhật phủ một chữ $X$ thứ nhất và thứ hai, trừ đi số lượng hình chữ nhật phủ cả hai chữ $X$.

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

### Subtask 3: $K \le 20$

Mở rộng subtask 2, xuất phát từ ý tưởng [bao hàm loại trừ](https://wiki.vnoi.info/vi/translate/he/Number-Theory-7), kết quả sẽ là: số lượng hình chữ nhật phủ ít nhất $1$ chữ $X$, trừ đi số lượng hình chữ nhật phủ ít nhất $2$ chữ $X$, cộng thêm số lượng hình chữ nhật phủ ít nhất $3$ chữ $X$, ...

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

## Bài 4: TITLE3

Tóm tắt đề bài: Cho một bảng gồm $N$ hàng và $M$ cột. Có $K$ ô bị đánh dấu trong bảng. Hãy đếm cách xếp các viên gạch kích thước $1 \times 2$ hoặc $2 \times 1$ sao cho các viên gạch xếp kín bảng, và không nằm đè lên các ô cấm.

> Bạn đọc nên tìm hiểu trước về quy hoạch động bitmask.

Nhận xét: Điều kiện $N \le 10$ khá "lạ", ta nghĩ đến trạng thái quy hoạch động: $dp[i][j]$ là số cách xếp đến hết hàng $i$ và trạng thái cột $i$ là $mask$.

Ta có thể chuyển trạng thái dễ dàng.

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