## Tác giả:
- Hà Phước Vũ - Trường THPT Chuyên Lê Quý Đôn, Đà Nẵng.
- Trần Tiến Khoa - Trường THPT Phan Châu Trinh, Đà Nẵng.
## I. Giới thiệu.
Sáng ngày 6/7/2024, kì thi Tin học trẻ Khu vực đã kết thúc sau khi diễn ra từ sáng đến chiều.
Là một thí sinh của kì thi, bản thân mình thấy:
- Đề rất hay và chủ yếu thiên về tư duy.
- So với đề năm ngoái, đề năm nay dễ hơn rất nhiều bởi số lượng thí sinh AC được $1$ trong $2$ bài đầu là có đáng kể.
Không dài dòng nữa, dưới đây là lời giải của $3$ bài.
## II. Lời giải.
### Bài 1. QUEENS.
##### Tags: branch and bound, math - 1100.
#### 1. Đề bài.
Cho một bàn cờ có kích thước $n \times n$, ô ở vị trí giao nhau của hàng $i$ và cột $j$ chứa một giá trị là $a_{i, j}$. Tiến hành đặt $k$ quân hậu lên bàn cờ trên bàn cờ sao cho không có $2$ con hậu nào tấn công nhau, và gọi $S$ là tổng các số trên các ô mà $k$ quân hậu nằm trên. Tìm giá trị lớn nhất của $S$.
Giới hạn:
- $1 \le k \le n \le 8$.
- $1 \le a_{i, j} \le 10^6$.
#### 2. Lời giải.
Ta sẽ đệ quy chọn ra $k$ cột trên bàng cờ để đặt $k$ quân hậu lên trên. Tại mỗi cột, ta sẽ tìm một hàng mà chưa có quân hậu nào nằm trên đó và đặt con hậu. Tuy nhiên điều đó là chưa đủ bởi quân hậu còn có thể tấn công theo hàng chéo. Vì vậy, ta sẽ kiểm tra đường chéo mà ô giao nhau giữa cột đang xét và hàng đang chọn có quân hậu nào tấn công hay không. Giả sử ta đang xét cột $i$ và chọn hàng $j$, ta sẽ cần phải xét $2$ trường hợp sau:
- Hàng chéo thứ $i+j-1$ xét từ ô trái dưới sang ô phải trên.
- Hàng chéo thứ $i-j+n+1$ xét từ ô trái trên sang ô phải dưới.
Nếu thỏa mãn cả $3$ điều kiện trên, ta sẽ đặt $1$ quân hậu trên ô đó và tiếp tục đệ quy. Nếu như không đặt được thì ta sẽ không tiếp tục đệ quy nữa và dừng lại bởi tiếp tục sẽ chả được gì.
Độ phức tạp thời gian của ý tưởng trên là xấp xỉ $O(C_n^k \times n!)$, còn bộ nhớ là xấp xỉ $O(n)$.
#### 3. Đánh giá.
Đây là một bài nhánh cận không quá khó, rất thích hợp để làm bài đầu tiên cho một kì thi. Qua một vài câu hỏi, mình nhận thấy đa số các bạn mắc các lỗi như sau.
- Tính sai độ phức tạp của code.
- Công thức hàng chéo bị sai hoặc quên mất có $2$ đường chéo.
Còn nguyên nhân mình bị TLE và đấm đến $10$ lần thì mình chịu <(").
### Bài 2. AKSEQ.
##### Tags: data structures, math - 1600.
#### 1. Đề bài.
Cho dãy $A^k$ là bản sao của một dãy $a$ gồm $n$ phần tử được lặp lại $k$ lần. Hãy đếm số vị trí $i$ $(1 \le i \le n\times k)$ thỏa mãn:
- $2 \times min(A^k_i, A^k_{i+1}, ..., A^k_{i+d-1}) > \frac{A^k_i+A^k_{i+1}+...+A^k_{i+d-1}}{d}$.
Giới hạn:
- $1 \le n, k \le 10^5$.
- $1 \le d \le n \times k$.
- $1 \le a_i \le 10^6$.
#### 2. Lời giải.
Để dễ dàng cho việc tính toán, ta có biến đổi như sau:
- $2 \times min(A^k_i, A^k_{i+1}, ..., A^k_{i+d-1}) > \frac{A^k_i+A^k_{i+1}+...+A^k_{i+d-1}}{d}$ thành $2 \times d \times min(A^k_i, A^k_{i+1}, ..., A^k_{i+d-1}) > A^k_i+A^k_{i+1}+...+A^k_{i+d-1}$
Để lấy min một đoạn $[i, i+d-1]$ trên dãy $A^k$, ta sẽ xét $2$ trường hợp sau:
- $d \ge n$ thì khi đó, min của đoạn $[i, i+d-1]$ sẽ luôn là min của dãy $a$ ban đầu.
- $d < n$ thì để lấy min một đoạn nhanh, ta có thể sử dụng deque hoặc cây phân đoạn.
Để lấy tổng một đoạn $[i, i+d-1]$ trên dãy $A^k$, ta sẽ xét $2$ trường hợp sau:
- $d \le n$ thì ta chỉ việc sử dụng mảng cộng dồn.
- $d > n$ thì ta sẽ lấy tổng theo tư tưởng của chia căn, trong đó mỗi block dãy $a$.
Ta nhận thấy dãy $A^k$ là dãy $a$ được lặp lại $a$ lần, vì vậy nếu vị trí $i$ thỏa mãn đề bài thì các vị trí $i+j\times n$ cũng sẽ thỏa mãn. Vì vậy, ta chỉ cần duyệt qua các vị trí $i$ từ $1$ đến $n$. Với mỗi vị trí $i$ thỏa mãn, các số $j$ thỏa mãn là:
- $i+j\times n + d - 1 \le n \times k$.
- $j\times n \le n \times k - d - i + 1$.
- $j \le \frac{n \times k - d - i + 1}{n}$.
Dễ dàng thấy từ công thức trên, số lượng số $j$ cho mỗi vị trí $i$ thỏa mãn là $\frac{n \times k - d - i + 1}{n}+1$.
Độ phức tạp thời gian của ý tưởng trên là $O(n \times log_2 n)$, còn bộ nhớ là xấp xỉ $O(n)$.
#### 3. Đánh giá.
Đây là một bài đếm cần tư duy khi bạn phải để ý rằng các vị trí $i$ sẽ bị trùng lặp.
### Bài 3. TBN.
##### Tags: dp-digit - 2000.
#### 1. Đề bài:
Biểu thức ngoặc là xâu chỉ gồm các kí tự `(`, `)`, `[`, `]`, `{`, `}`. Biểu thức ngoặc đúng và bật của biểu thức ngoặc được định nghĩa một cách đệ quy như sau:
- Biểu thức rỗng là biểu thức ngoặc đúng và có bậc bằng $0$.
- Nếu `A` là biểu thức ngoặc đúng có bậc bằng $k$ thì `(A)`, `[A]`, `{A}` cũng là một biểu thức ngoặc đúng có bậc bằng $k+1$.
- Nếu `A` và `B` là hai biểu thức ngoặc đúng có bậc tương ứng là $k_1$ và $k_2$ thì `AB` cũng là một biểu thức ngoặc đúng có bậc bằng $max(k_1, k_2)$.
Cho $2$ số nguyên dương $n, k$ và một biểu thức ngoặc đúng có độ dài $n$ có bậc $k$ là $S$. Gọi $f$ là tập chứa tất cả các biểu thức ngoặc đúng có độ dài $n$ và có bậc $k$ được sắp xếp theo thứ tự tăng dần, nhiệm vụ của bạn là tìm vị trí của $S$ trong tập $f$.
Giới hạn:
- $1 \le n \le 200; 1 \le k \le 5$.
#### 2. Lời giải:
Gọi $dp(i, a)$ là số cách dựng dãy ngoặc từ vị trí $i$ đến $n$ có dãy các ngoặc mở chưa đóng trong dãy ngoặc từ $1$ đến $i-1$ là $a$. Khi đó, ta sẽ có công thức truy hồi như sau:
- $dp(i, a)$ $+$$=$ $dp(i+1, b)$ với $b$ là dãy $a$ sau khi đóng dấu ngoặc ở cuối của $a$, tức là điền dấu ngoặc đóng tương ứng tại vị trí $i$. Điều kiện để tính là $|a| \ge 1$.
- $dp(i, a)$ += $dp(i+1, b)$ với $b$ là $a$ khi thêm một trong $3$ dấu ngoặc mở. Điều kiện để tính là $|a| < k$ và $|a| \le n-i+1$.
Ta còn có một nhận xét quan trọng:
- Số lượng dấu ngoặc mở trong $a$ tại mọi thời điểm luôn không vượt quá $k$ $(|a| <= k)$ bởi nếu không thì khi dãy được dựng xong sẽ có bậc lớn hơn $k$.
Gọi $f(i)$ là số thứ tự của dãy ngoặc đúng đầu tiên có tiền tố là dãy $s_1s_2...s_{i}$. Khi đó, ta sẽ có công thức với $a$ là dãy ngoặc mở chưa đóng của dãy ngoặc $s_1s_2...s_i$ :
- $f(i)$ $=$ $f(i-1)$ $+$ $dp(i+1, b)$ với mọi $b = a + c$ $(c \in \{$`(`, `[`, `{`$\}$ $|$ $c < s_i)$.
- $f(i)$ $=$ $f(i-1)$ $+$ $dp(i+1, b)$ với $b$ là dãy $a$ sau khi đóng dấu ngoặc ở cuối của $a$ . Điều kiện để tính là $c < s_i$ với $c$ là dấu ngoặc đóng ứng với ngoặc mở ở cuối dãy $a$.
Cuối cùng, kết quả cần tìm của ta sẽ là là $f(n)$. Lưu ý rằng kết quả này có thể rất lớn trong một số trường hợp nên cần phải cài đặt **xử lý số lớn**.
Độ phức tạp thời gian của ý tưởng trên $O(n\times \frac{3^{k+1}-1}{2} + n)$, còn bộ nhớ là $O(n\times \frac{3^{k+1}-1}{2})$. Dưới đây là code tham khảo của bài.
```cpp=
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define The_Moon ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mkp make_pair
#define fi first
#define se second
#define lll string
lll operator + (lll a, lll b){
if(a.size() < b.size())a.insert(0, b.size()-a.size(), '0');
if(a.size() > b.size())b.insert(0, a.size()-b.size(), '0');
int c = 0, du = 0;
for(ll i = a.size()-1; i >= 0; i--){
c = a[i]+b[i] -'0'-'0' + du;
a[i] = char((c%10)+'0');
du = c/10;
}
if(du)a = char(du + '0') + a;
return a;
}
ll n, k;
stack<ll> operator --(stack<ll> a){
a.pop();
return a;
}
stack<ll> operator +(stack<ll> a, int x){
a.push(x);
return a;
}
map<pair<ll,stack<ll>>, pair<lll, bool> > m;
lll cal(ll i, stack<ll> v){
if(m[mkp(i, v)].se)return m[mkp(i, v)].fi;
if(i > n)return (v.empty() ? "1" : "0");
lll res = "0";
if(n-i+1 >= v.size() && v.size() < k)for(int j = 0; j < 3; j++)res = res + cal(i+1, v + j*2);
if(v.size())res = res + cal(i+1, --v);
m[mkp(i, v)].fi = res;m[mkp(i, v)].se = 1;
return res;
}
int main(){
The_Moon
m.clear();
cin >> n >> k;
lll res = "1";
string s; cin >> s;
for(auto& i : s){
if(i == '(')i = 0;
else if(i == ')')i = 1;
else if(i == '[')i = 2;
else if(i == ']')i = 3;
else if(i == '{')i = 4;
else if(i == '}')i = 5;
}
stack<ll> base;
s = '*'+s;
for(ll i = 1; i <= n; i++){
for(ll j = 0; j < s[i]; j+=2)
if(n-i+1 >= base.size() && base.size() < k)res = res + cal(i+1, (base + j));
if(base.size() && base.top()+1 < s[i])res = res + cal(i+1, --base);
if((s[i]&1))base = --base;
else base = base + s[i];
}
cout << res;
}
```
#### 3. Đánh giá.
Đây là một bài Digit Dp trá hình khá hay và cần tư duy tốt. Để hiểu và làm được thì bạn cần phải hiểu rõ bản chất của Digit Dp.
## III. Tổng kết.
Chỉ vậy thôi, chúc bạn thành công full đề Tin học trẻ khu vực bảng B 2024 nhé.
Sign in with Wallet
Connect another wallet