# Lời giải đề thi thử Tuyển sinh 10 trường THPT chuyên Đại học Sư phạm Hà Nội - Môn Tin học

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

## Bài 1: Số đặc biệt

Tóm tắt đề bài: Cho số nguyên dương $n$, hãy in ra các ước $x$ của $n$ mà thỏa mãn $x - 1$ hoặc $x + 1$ cũng là ước của $n$.

### Subtask 1: $n \le 10^6$

Duyệt $i$ từ $1$ đến $n$ và kiểm tra xem $i$, $i - 1$, $i + 1$ có phải ước của $n$ hay không.

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

### Subtask 2: $n \le 10^{12}$

Ta duyệt đến $\sqrt n$ để có một danh sách các ước của $n$. Ta sắp xếp danh sách này lại.

Với mỗi phần tử của danh sách, ta chỉ cần xem phần tử ngay trước nó, và phần tử ngay sau nó có chênh lệch đúng một đơn vị hay không. Nếu có, đây là một phần tử thỏa mãn.

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

### Subtask 3: $n \le 10^{18}$.

Ta cần một cách để lấy ra mọi ước của $n \le 10^{18}$.

Bản chất, nếu ta có thể phân tích $n$ ra thừa số nguyên tố: $n = p_1^{d_1} \times p_2^{d_2} \times ... \times p_k^{d_k}$ thì ta có thể gọi đệ quy: với mỗi thừa số ta chọn ra một số mũ. Từ đó ta sinh ra được mọi ước của $n$.

Vấn đề đặt ra là phân tích $n$ ra thừa số nguyên tố. Ta có thể sử dụng [thuật toán Pollard-Rho](https://wiki.vnoi.info/vi/algo/math/integer-factorization) để làm điều này.

Một cách khác (credit: [Phước Vũ](https://www.facebook.com/Not.Miku.8909)) là: Một số nguyên dương $n$ có ước đặc biệt là $x$ sẽ có dạng $x \times (x + 1) \times k$, với $k$ cũng nguyên dương.

Bằng phản chứng, ta có thể chứng minh được $min (x, k) \le 10^6$. Ta có thể duyệt $x$, hoặc duyệt $k$ để tính kết quả. Cần cẩn thận để tránh tính trùng.

Độ phức tạp $O$ ($\sqrt {\sqrt n}$) hoặc $O$ ($t \times 10^6$).

## Bài 2: Đường tròn

Tóm tắt đề bài: Cho $n$ điểm đen và $n$ điểm trắng trên mặt phẳng tọa độ. Tìm hình tròn có bán kính nhỏ nhất mà có số lượng điểm đen trong nó, bằng số lượng điểm trắng trong nó.

**Nhận xét:** Bán kính tối ưu luôn có một điểm nằm trên viền của đường tròn.

Điều này có thể dễ dàng quan sát thấy. Nếu không có điểm nào nằm trên viền của đường tròn, ta có thể giảm bán kính và được kết quả tối ưu hơn.

Vì vậy, ta sẽ duyệt $dist$ là khoảng cách từ tâm đến một điểm trên đường tròn. Sau đó, sử dụng **tìm kiếm nhị phân** để xem có bao nhiêu điểm nằm trong đường tròn. Nếu số lượng điểm đen bằng số lượng điểm trắng, ta in ra kết quả.

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

## Bài 3: Cộng dãy

Tóm tắt đề bài: Cho mảng $a$ gồm $n$ phần tử. Có $q$ truy vấn, mỗi truy vấn là cộng cả mảng lên $x$ đơn vị ($x$ có thể âm). Sau mỗi truy vấn, hãy in ra $\sum |a_i|$.

### Subtask 1: $n, q \le 5000$

Thực hiện y như những gì đề bài bảo.

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

### Subtask 2: $n, q \le 5 \times 10^5$

Ta hoàn toàn có thể sắp xếp lại mảng $a$.

Gọi $add$ là tổng giá trị ta phải cộng thêm vào mảng $a$ cho tới bây giờ. Dễ thấy, kết quả là |tổng các số trong mảng $a$ < $0$| + (tổng các số trong mảng $a \ge 0$).

Do mảng $a$ đã được sắp xếp, ta sẽ **tìm kiếm nhị phân** để tìm ra chỉ số $i$ lớn nhất mà $a_i + add < 0$. Từ phần tử $i$ trở về trước, kết quả sẽ phải đảo dấu; từ phần tử thứ $i + 1$ trở về sau, kết quả không cần đảo dấu.

Để tính toán nhanh tổng này, có thể sử dụng **tổng tiền tố**.

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

## Bài 4: Lắp đặt trạm thu phát sóng

Tóm tắt đề bài: Chọn ra một vài trạm phát sóng sao cho:
- Khoảng cách giữa hai trạm phát sóng bất kỳ $\ge k$.
- Tổng lợi nhuận của các trạm phát sóng đó là lớn nhất.

### Subtask 1: $n \le 1000$

Gọi $dp_i$ là lợi nhuận lớn nhất khi xét đến trạm phát sóng thứ $i$, bắt buộc chọn trạm phát sóng thứ $i$.

Ta thấy, $dp_i = max (a_i, dp_j + a_i)$ với điều kiện $1 \le j \le i - 1$ và $p_i - p_j \ge k$.

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

### Subtask 2, 3: $n \le 10^6$

Ta có thể duy trì $x$, là vị trí lớn nhất thỏa mãn $p_i - p_x \ge k$ bằng **hai con trỏ.**

Lúc này, ta có công thức truy hồi mới: $dp_i = max (a_i, max (dp_1, dp_2, ..., dp_x) + a_i)$.

Để xử lý nhanh phần này, ta gọi $f_i = max (dp_1, dp_2, ..., dp_i)$.

Lúc này, công thức truy hồi là: $dp_i = max (a_i, f_x + a_i)$.

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

**Lưu ý: Dữ liệu vào rất lớn, mình đã chỉnh giới hạn thời gian ở 5 giây. Nếu muốn cải tiến hơn nữa, có thể sử dụng [fast input](https://codeforces.com/blog/entry/120183), sẽ AC trong 1 giây.**