Tác giả:

• Hà Phước Vũ - Lớp
  $9/5$, trường THCS Tây Sơn, Đà Nẵng.

I. Giới thiệu.

Sáng ngày

$4/6/2024$, kỳ thi Tuyển Sinh chuyên Tin 10 năm 2024 của Đà Nẵng vừa kết thúc và diễn ra trong

$2.5$ giờ liên tiếp.

Là một thí sinh của kỳ thi, mình có một số đánh giá độ khó của đề như sau:

• Đề không dễ và rất hay, chưa thấy đề năm nào hay như vậy.
• So với đề năm ngoái, đề năm nay dễ hơn khi không có sự xuất hiện của Hash và FFT.

Không dài dòng nữa, dưới đây là lời giải của cả

$4$ bài.

II. Lời giải.

Bài 1: Số chuẩn 1.

• Tags: Digit Dp, math -
  $1200$.

1. Đề bài.

Một số nguyên dương

$n$ được gọi là số chuẩn

$1$

$n$ nếu như tổng chữ số của

$n$ tại vị trí lẻ trừ cho tổng chữ số của

$n$ tại vị trí chẵn là

$1$.

Cho

$2$ số nguyên dương

$a,b$, nhiệm vụ của bạn là đếm số lượng số chuẩn

$1$ trong đoạn

$[a,b]$.

2. Lời giải.

Ngoài cách giải dưới ra thì vẫn còn có một cách giải bằng toán, và bạn có thể tham khảo bên TLEoj.

Trước tiên, ta định nghĩa

$F(n)$ là số lượng số hình mẫu không quá

$n$. Khi đó đáp án sẽ là

$F(b)-F(a-1)$.

Về phần tính

$F(n)$, gọi

$dp[idx][tight][dis]$ là số lượng số chuẩn

$1$ khi ta đang xét chữ số ở vị trí

$idx$ của số hình mẫu, và

$dis$ là hiệu giữa tổng chữ số ở vị trí lẻ và chẵn. Khi thêm

$1$ chữ số

$d$ vào bên phải chữ số hình mẫu, ta sẽ có

$2$ trường hợp như sau:

• Chữ số đó được thêm vào vị trí lẻ (khi đó
  $idx\mathrm{\%}2=0$) thì công thức truy hồi là
  $dp[idx+1][tight][dis+d]$
  $+=$
  $dp[idx][tight][dis]$.
• Chữ số đó được thêm vào vị trí chẵn (khi đó
  $idx\mathrm{\%}2=1$) thì công thức truy hồi là
  $dp[idx+1][tight][dis-d]$
  $+=$
  $dp[idx][tight][dis]$.

Đáp án của chúng ta sẽ là

$dp[len][0][1]+dp[len][1][1]$ với

$len$ là số lượng chữ số của

$n$.

Lưu ý rằng

$dis$ có thể âm nên bạn nên cộng tất cả các giá trị

$dis$ cho một hằng số nào đó (mình để xuất là

$90$ nha).

Độ phức tạp của ý tưởng trên là

$O((lo{g}_{10}a+lo{g}_{10}b)\times 2\times 180\times 9)$.

3. Đánh giá.

Nếu như đã biết Dp chữ số thì đây là một bài không quá khó để giải, chỉ cấn ở chỗ bạn có nghĩ đến việc là xử lý trên

$dis$ hay không.

Bài 2: Từ vựng.

• Tags: string, counting -
  $900$.

1. Đề bài.

Cho xâu

$s$ gồm

$n$ kí tự, hãy đếm số lượng xâu con thỏa mãn:

• Bắt đầu bằng
  $1$ phụ âm và kết thúc bằng
  $1$ nguyên âm.
• Bắt đầu bằng
  $1$ nguyên âm và kết thúc bằng
  $1$ phụ âm.

Nguyên âm (vowels) là các kí tự u, e, o, a, i trong bảng chữ cái La tinh.

2. Lời giải.

Bài này quá cơ bản rồi.

Gọi

$a$ và

$b$ lần lượt là số lượng nguyên âm và phụ âm xuất hiện trong xâu

$s$, dễ dàng thấy đáp án là

$a\times b$.

Độ phức tạp của ý tưởng trên là

$O(n)$ với

$n$ là độ dài của

$s$.

3. Đánh giá.

Bài này là một bài rất cơ bản nên nếu bạn không giải được, bạn cần xem lại cách học tin của mình nhé. Còn nếu bạn skill issue mất điểm thì hết cứu thật rồi.

Bài 3: Nobita.

• Tags: dp -
  $1700$.

1. Đề bài.

• Đề bài tại Codeforces - 1974E.

2. Lời giải.

Nhận thấy

$x$ rất lớn nên ta không thể Dp trên

$x$ và

$c_i$, thay vì đó ta sẽ sử dụng Kĩ thuật Dp đảo nhãn. Nghĩa là từ

$c_i$ tìm

$h_i$ lớn nhất thì ta sẽ từ

$h_i$ tìm

$c_i$ nhỏ nhất.

Gọi

$dp[j]$ là tổng trọng lượng các bảo bối ít nhất để tổng các giá trị phép thuật là

$j$. Ta sẽ duyệt qua các bảo bối từ

$1$ đến

$n$. Nhận thấy tại món bảo bối thứ

$i$, ta chỉ cần tính giá trị của

$dp[h_i]$ cho đến

$dp[h_1+h_2+...+h_i]$. Khi đó, ta sẽ duyệt

$j$ ngược từ

$h_1+h_2+...+h_i$ về

$h_i$ và có công thức truy hồi như sau:

• $dp[j]=min(dp[j],dp[j-h_i]+c_i)$ nếu
  $dp[j-h_i]+c_i\le (i-1)\ast x$.
• Đặt
  $dp[j]=inf$ nếu không tồn tại cách nào.

Đáp án của chúng ta sẽ là giá trị

$j$ lớn nhất thỏa mãn tồn tại một cách chọn các bảo bối để có tổng các giá trị phép thuật là

$j$ (hay

$Dp[j]\ne inf$).

Độ phức tạp của ý tưởng trên sẽ là

$O(\sum _{i=1}^n\sum _{j=1}^{i-1}{h}_i)$.

3. Đánh giá.

Đây là một bài khá khó nếu như các bạn chưa thành thạo Dp hay là chưa làm nhiều các bài tập về Dp. Đặc biệt kĩ thuật Đảo nhãn Dp sẽ khá lạ đối với phần lớn học sinh THCS hiện nay.

Bài 4: Trò chơi.

• Tags: prefix-sum, bin-search -
  $1800$.

1. Đề bài.

Cho dãy

$a$ gồm

$n$ phần tử, hãy tìm số nguyên dương

$x$ thỏa mãn nó là trung vị của một dãy con liên tiếp có độ dài không bé hơn

$k$ của dãy

$a$.

Trung vị của một dãy

$a$ gồm

$n$ phần tử là phần tử ở vị trí

$\lfloor \frac{n+1}{2}\rfloor$ của dãy

$a$ khi được sắp xếp lại.

2. Lời giải.

Ta sẽ chặt nhị phân kết quả, cụ thể ta sẽ giá trị

$mid$ từ

$1$ đến

$n$ và kiểm tra xem có dãy con liên tiếp có độ dài không bé hơn

$k$ nào thỏa mãn trung vị của nó không bé hơn

$mid$ hay không. Nếu có thì đáp án cần tìm chắc chắn sẽ ở trong đoạn

$[mid,r]$, không thì đáp án cần tìm chắc chắn sẽ ở trong đoạn

$[l,mid-1]$.

Với mỗi giá trị

$mid$, ta sẽ gọi dãy

$b$ là dãy thỏa mãn

$b_i=-1$ nếu

$a_i<mid$ và

$b_i=1$ nếu

$a_i\le mid$. Dễ dàng thấy nếu dãy

$b$ tồn tại một dãy con liên tiếp có độ dài không bé hơn

$k$ thỏa mãn tổng của nó lớn hơn

$0$, thì chính dãy đó sẽ có giá trị trung vị không bé hơn

$mid$. Để làm điều này, ta chỉ việc sử dụng tổng tiền tố và min tiền tố.

Độ phức tạp của ý tưởng trên là

$O(n\times lo{g}_{2}n)$.

3. Đánh giá.

Đây là một bài khá hay nếu bạn không đọc sai đề.

III. Tổng kết.

Căn cứ vào độ khó và kết quả từ miệng của các bạn thí sinh, mình dự đoán số điểm mà phần lớn các bạn sẽ đạt được là từ

$4$ đến

$7$.

Ưu điềm của đề:

• Đề phân hóa mức độ giỏi của thí sinh khá tốt.
• Trừ
  $2$ bài đầu ra thì
  $2$ bài còn lại khá hay.

Nhược điểm của đề:

• Dp đảo nhãn ở bài
  $3$.
• Subtask được chia vẫn chưa được tốt.
• Giới hạn của bài
  $4$ bị sai, cụ thể là chỗ
  $1\le a_i\le n$.

Chỉ vậy thôi, chúc bạn thành công full đề Tuyển Sinh chuyên Tin 10 năm 2024 của Đà Nẵng nhé.