## I. Mở đầu.
Chiều ngày 20/02/2025, kì thi Tin HSG 9 Đà Nẵng đã kết thúc sau $150$ phút thi.

Sau khi đọc đề của môn Tin và suy nghĩ một chút, bản thân mình thấy:
- Mặc dù không quá khó nhưng so với năm ngoái, đề năm nay khó hơn chút.
- $2$ bài đầu khá cơ bản, $2$ bài sau yêu cầu thí sinh cần có tính cẩn thận và biết dùng não.

Không nói nhiều nữa, dưới đây sẽ là đề bài và lời giải chi tiết của cả $4$ bài.
## II. Lời giải.
### Bài 1. Kí tự.
##### Tags: string - 800.
#### 1. Đề bài.
Cho xâu $s$ gồm các kí tự chữ cái tiếng Anh in hoa, nhiệm vụ của bạn là tìm ra những kí tự trong bảng chữ cái không xuất hiện trong $s$.

Các kí tự được in ra phải theo thứ tự tăng dần.

Giới hạn:
- $1 \le |s| \le 10^5$.
#### 2. Lời giải.
Ta sẽ sử dụng mảng đánh dấu, $vis[c]$ là $1$ nếu kí tự $c$ xuất hiện trong $s$ và $0$ nếu ngược lại. Để làm điều này, ta chỉ việc duyệt qua xâu $s$ và làm như trên.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(|s|)$.
- Bộ nhớ: $O(26)$.
#### 3. Đánh giá.
- Đây là một bài duyệt xâu khá cơ bản mà những bạn mới học cũng có thể làm được. Tuy nhiên, nếu không cẩn thận thì bạn vẫn có thể mắc các lỗi cực kì ngớ ngẫn như nhầm lẫn kí tự là in thường.
### Bài 2. Số tròn chục.
##### Tags: math - 900.
#### 1. Đề bài.
Cho $2$ số tự nhiên $l$ và $r$, hãy đếm số lượng số tròn chục trong đoạn $[l+1, r-1]$.

Giới hạn:
- $0 \le l < r \le 10^{12}$.
#### 2. Lời giải.
Nhắc lại: Số tròn chục là những số tự nhiên chữ số tận cùng là $0$.

Ta gọi $F(n)$ là số lượng số tròn chục không lớn hơn $n$ và khi đó, ta có công thức $F(n) = \lfloor \frac{n}{10} \rfloor$. Với $F(n)$, đáp án của chúng ta sẽ là $F(r-1)-F(l)$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(1)$.
- Bộ nhớ: $O(1)$.

#### 3. Đánh giá.
- Đây là một bài Toán khá cơ bản, tuy nhiên các bạn có thể sai nếu như không đọc kĩ đề bởi vì ta cần đếm những số lớn hơn $l$ và bé hơn $r$. Ngoài ra, để sai kiểu dữ liệu cũng sẽ khiến bạn mất điểm bài này.
### Bài 3. Tổng liên tiếp.
##### Tags: math - 1100.
#### 1. Đề bài.
Cho dãy $a$ gồm $n$ phần tử $a_1, a_2, ..., a_n$ và $2$ số nguyên dương $p$ và $k$. Đặt dãy $b$ là dãy $a_1, a_2, ..., a_n, a_1, a_2, ..., a_n, a_1, ...$, nhiệm vụ của bạn là tính tổng các phần tử của $b$ từ vị trí $p$ đến vị trí $p+k-1$ chia lấy dư cho $10^9+7$.

Giới hạn:
- $1 \le n \le 10^5$.
- $1 \le p, k \le 10^{18}$.
#### 2. Lời giải.
Ta gọi $F(i)$ là tổng các phần tử của $b$ từ $1$ đến $i$. Khi đó, kết quả mà ta cần tìm sẽ là $F(p+k-1)-F(p-1)$.

Nhận thấy rằng dãy $b$ chỉ là dãy $a$ lặp lại nhiều lần, ta có thể chia việc tính $F(i)$ thành $2$ phần sau:
- Phần $1$: Đoạn $[1, i]$ chứa bao nhiêu dãy $a$.
- Phần $2$: Phần tiền tố của $a$ mà đoạn $[1, i]$ phủ ở cuối.

Ở phần $1$, ta có thể tìm ra số dãy $a$ mà đoạn $[1, i]$ chứa sẽ là $\lfloor \frac{i}{n} \rfloor$.

Ở phần $2$, ta sẽ đạt $i = i\%n$ vì ta chỉ quan tâm phần tiền tố mà đoạn $[1, i]$ phủ $a$ ở cuối thôi mà. Sau khi chia lấy dư, ta có thể nhận thấy rằng phần tiền tố đó chính là $a_1, a_2, ..., a_i$ ($i = 0$ thì không chứa gì).

Dựa vào $2$ phần trên, ta có công thức tính $F(i)$ là:
- $(a_1+a_2+...+a_n)\times \lfloor \frac{i}{n} \rfloor + (a_1+a_2+...+a_{i\%n})$.

Có được công thức trên, ta có thể dễ dàng tìm ra kết quả.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(n)$.
- Bộ nhớ: $O(n)$.

Thử thách: Bạn có thể giải quyết bài toán nhưng là thêm $q$ truy vấn với mỗi truy vấn yêu cầu giải quyết bài toán với $(p, k)$ khác nhau không?
#### 3. Đánh giá.
- Đây là một bài trên dãy khá nâng cao so với các bài trước và cần sử dụng não một chút, rất thích hợp để phân loại thí sinh.
- Nếu không cẩn thận hay đọc kĩ đề, bạn chắc chắn sẽ mất đi số điểm rất lớn như mắc phải lỗi quên chia lấy dư cho $10^9+7$ hay là không để ý rằng có thể $p > n$.
### Bài 4. Chiến binh.
##### Tags: dp, math - 1200.
#### 1. Đề bài.
Ở một vương quốc nọ, số lượng binh lính cấp $1$ mà họ sở hữu vào ngày đầu tiên (ngày $0$) là $n$. Trong các ngày tiếp theo, những điều sau sẽ xảy ra:
- Mỗi binh lính cấp $i$ sẽ huấn luyện và chiêu mộ $i$ binh lính cấp $1$. Những binh lính mới này đều sẽ được huấn luyện vào ngày hôm sau.
- Đồng thời, binh lính cấp $i$ sẽ tiến hoá thành binh lính cấp $i+1$.

Nhiệm vụ của bạn là xác định só lượng binh lính chia lấy dư cho $10^9+7$ sau $k$ ngày, hay là ở ngày thứ $k$.
#### 2. Lời giải.
Khi ta thử nháp ra từ ngày $0$ đến ngày $3$, ta sẽ có:
- Ngày $0$: $n$ cấp $1$.
- Ngày $1$: $n$ cấp $2$, $n$ cấp $1$.
- Ngày $2$: $n$ cấp $3$, $n$ cấp $2$, $3n$ cấp $1$.
- Ngày $3$: $n$ cấp $4$, $n$ cấp $3$, $3n$ cấp $2$, $8n$ cấp $1$.

Tổng của những ngày trên sẽ lần lượt là $n, 2n, 5n, 13n$. Dễ dàng thấy với tính chất của việc huấn luyện và chiêu mộ binh lính này, ta có số binh lính ở ngày thứ $k$ là $F_{2k+1}\times n$ với $F_i$ là số Fibonacci thứ $i$.

Nhắc lại: Dãy số Fibonacci là dãy số sau:
- $F_i = 1$ với $1 \le i \le 2$.
- $F_i = F_{i-1}+F_{i-2}$ với $i > 2$.

Để tính $F_{2k+1}$, ta có thể sử dụng Quy hoạch động. Cụ thể, ta gọi $dp[i]$ là số thứ $i$ và công thức truy hồi của ta sẽ là:
- $dp[i] = dp[i-1]+dp[i-2]$.

Với trạng thái cơ sở là $dp[1] = dp[2] = 1$. Thêm vào đó, bạn cần phải chia lấy dư khi tính $dp[i]$ bởi vì đề bài yêu cầu và $F_i$ là một hàm tăng rất nhanh. Sau khi tính xong, kết quả của chúng ta là $dp[2k+1]\times n$.

Độ phức tạp của ý tưởng trên là:
- Thời gian: $O(2k+1)$.
- Bộ nhớ: $O(2k+1)$.

Thử thách: Bạn có thể giải quyết bài toán nhưng là thêm $q$ truy vấn với mỗi truy vấn yêu cầu giải quyết bài toán với $(n, k)$ khác nhau không?
#### 3. Đánh giá.
- Đây là một bài Quy hoạch động khá cơ bản khi đã biết được công thức tìm kết quả, tuy nhiên sẽ khá ấy nếu như không ngồi nháp ra. Ngoài ra, bài này cũng rất thích hợp trong việc phân loại thí sinh.
- Nếu không cẩn thận hay đọc kĩ đề, bạn chắc chắn sẽ mất đi số điểm rất lớn như mắc phải lỗi quên chia lấy dư cho $10^9+7$.
## III. Tổng kết.
Chỉ vậy thôi, hi vọng rằng các bạn học được thêm một số thứ gì đó từ bài viết này. Ngoài ra thì, chúc các bạn có thể full đề này luôn :Đ