Tác giả:

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

Người kiểm thử:

• Trần Tiến Khoa - Lớp
  $9/3$, trường THCS Lương Thế Vinh, Đà Nẵng.

I. Giới thiệu.

• Đề bài tại đây.

Chiều ngày

$9/5/2024$, kỳ thi THT bảng B Thành phố Đà Nẵng vừa kết thúc và diễn ra trong

$2$ 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à chủ yếu thiên về giải thuật nhiều hơn là tư duy.
• So với đề năm ngoái, đề năm nay khó hơn khi có sự xuất hiện của Cây phân đoạn (Segment Tree) ở bài
  $3$ (và kĩ thuật nén số nữa) và bài
  $4$ không có nổi
  $1$ người ăn
  $100\mathrm{\%}$.
• Mình chỉ làm được hết
  $3$ bài đầu, còn bài
  $4$ thì chưa nên cách giải bài
  $4$ là chưa hoàn chỉnh nhé.

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ố độc lập.

• Tags: brute -
  $800$.

1. Đề bài.

Cho số nguyên dương

$n$, hãy tìm số nguyên dương nhỏ nhất lớn hơn

$n$ có các chữ số phân biệt với nhau.

2. Lời giải.

Bài này chỉ đơn giản là cày trâu thôi, bạn duyệt các số nguyên dương từ

$n+1$. Số nào thỏa mãn thì dừng lại và in ra nó (gọi số đó là

$ans$).

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

$O(ans-n)$, đừng lo vì

$ans-n$ sẽ luôn không quá

$354=10234-9980$. Dưới đây là code tham khảo (không có phần đọc tên file).

def check(n): 
    st, ln = set(), 0 
    for i in str(n):
        st.add(i)
        ln += 1
    if ln == len(st): return true
    return false
n = int(input())
n += 1
while true:
    if check(n) == true: 
        break
    n += 1
print(n)
#Python 3.

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 2: Mật thư.

• Tags: string -
  $800$.

1. Đề bài.

Cho xâu

$S$ gồm các từ và các dấu cách để ngăn cách các từ. Gọi

$S^{{}^{\prime }}$ là xâu chứa các từ trong

$S$ bị đảo ngược thứ tự. Nhiệm vụ của bạn là in ra

$S^{{}^{\prime }}$ và vị trí

$p$ nhỏ nhất sao cho

$S_p^{{}^{\prime }}$ có độ dài lớn nhất.

2. Lời giải.

Bài này thì không có gì để nói, ta chỉ cần bỏ các từ của xâu

$S$ vào một mảng rồi in nó theo thứ tự ngược lại. Đồng thời trong lúc đó, ta cũng sẽ tìm vị trí

$p$ nhỏ nhất sao cho

$S_p^{{}^{\prime }}$ có độ dài lớn nhất.

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

$O(n)$. Dưới đây là code tham khảo (không có phần đọc tên file).

s = input().split()
pos, ln = 0, 0
for i in range(len(s)-1, -1, -1):
    print(s[i], end = " ")
    if len(s[i]) >= ln:
        ln = len(s[i])
        pos = i+1
print("")
print(pos)
#Python 3.

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: Cặp số thuận nghịch.

• Tags: data structures -
  $1600$.

1. Đề bài.

Cho dãy

$a$ gồm

$n$ phần tử, hãy đếm số cặp

$(u,v)$ thỏa mãn:

• $1\le u<v\le n$.
• $a_u>a_v$.

2. Lời giải.

Subtask

$1$ và

$2$ thì không có gì đáng nói, nên ta sẽ đến với subtask

$3$ luôn.

Trước hết, ta sẽ nén lại các phần tử của dãy

$a$. Để dễ hình dung thì ví dụ với dãy

$a=[6,9,4,2]$ thì ta sẽ nén lại thành

$a=[3,4,2,1]$. Ta nhận thấy

$|a_i-a_j|$

$(1\le i<j\le n)$ không hề ảnh hương đến bài toán. Vì vậy khi nén,

$|a_i-a_j|<n$ thay vì lớn hơn như trước. Vậy tại sao lại phải nén, bây giờ ta đến với cách giải của bài này.

Ta sẽ duyệt

$i$ từ

$n$ về

$1$. Gọi

$cnt[a_i]$ là số phần tử

$a_j$ thỏa mãn

$a_i=a_j$

$(i\le j\le n)$. Dễ dàng thấy, số phần tử

$a_j$ thỏa mãn

$a_j<a_i$

$(i<j\le n)$ sẽ là

$cnt[1]+cnt[2]$

$+$

$...$

$+$

$cnt[a_i-1]$. Và để tính số phần tử đấy nhanh, ta có thể sử dụng Cây phân đoạn (Segment Tree). Và để cập nhật

$cnt[a_i]$ lên

$1$, ta cũng chỉ cần thực hiện trên cùng

$1$ cây. Từ đó dễ dàng thấy bài này đã được đưa về dạng bài Range Sum Queries and Point Update. Đồng thời ta thấy việc nén các phần tử

$a_i$ cho phép chúng ta thao tác với nó trên cây vì

$a_i\le n$. Nếu

$a_i>n$ hay thậm chí là

$a_i>{10}^9$ thì điều này là bất khả thi.

Ngoài việc sử dụng Cây phân đoạn (Segment Tree) như trên, bạn vẫn có thể sử dụng Cây chỉ số nhị phân (Fenwick Tree) như mình khi ở trong phòng thi.

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

$O(n\times lo{g}_{2}n)$. Dưới đây là code tham khảo (không đọc tên file), và mình cài Cây chỉ số nhị phân (Fenwick Tree) nhé. Với cây còn lại thì làm tương tự.

#include <bits/stdc++.h>
#define ll long long
#define get_an_ac ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int lim = 100000;
ll bit[lim+5], a[lim+5]; vector<ll> com;
void update(int pos) {
    while (pos <= lim) {
        bit[pos]++;
        pos += (pos&-pos);
    }
}
ll query(int pos) {
    ll res = 0;
    while (pos > 0) {
        res += bit[pos];
        pos -= (pos&-pos);
    }
    return res;
}
int main() {
    get_an_ac
    int n; cin >> n; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        com.push_back(a[i]);
    }
    sort(com.begin(), com.end());
    ll ans = 0;
    for (int i = n; i >= 1; i--) {
        a[i] = lower_bound(com.begin(), com.end(), a[i])-com.begin()+1;
        ans += query(a[i]-1);
        update(a[i]);
    }
    cout << ans << "\n";
    return 0;
}

3. Đánh giá.

Đây là một bài khá cơ bản nếu thí sinh đã biết Segment Tree và kĩ thuật nén số. Còn đối với các bạn không biết thì đây sẽ là một bài khó, tuy nhiên

$60\mathrm{\%}$ số điểm của bài là cày trâu nên nếu cẩn thận thì vẫn dễ dàng có điểm. Vì vậy, đây là một bài phân hóa mức độ giỏi của thí sinh khá tốt.

Lúc đầu đọc bài này mà mình bất ngờ, do mình cứ nghĩ THT Thành phố Đà Nẵng ra kiến thức khó nhất cũng chỉ là Dp cơ bản thôi chứ bởi các đề năm trước thường ra như vậy (không có ý nghĩ khinh thường, chỉ là ý kiến cá nhân).

Bài 4: Trò chơi.

• Tags: dp, dnc, greedy -
  $?$ (cái này mình không rõ ).

1. Đề bài.

Cho dãy

$a$ gồm

$n$ phần tử,

$a_1$ có

$1$ phần tử liền kề là

$a_2$ và

$a_n$ có

$1$ phần tử liền kề là

$a_{n-1}$. Còn lại với mọi

$2\le i\le n-1$ sẽ có

$2$ phần tử liền kể là

$a_{i-1}$ và

$a_{i+1}$. Bạn được thực hiện

$3$ thao tác sau trên dãy

$a$ vô số lần:

• Chọn một phần tử
  $a_i$ có
  $2$ phần tử liền kề chưa được chọn thì điểm số của bạn tăng lên
  $\frac{a_{i-1}+a_{i+1}}{2}$. Sau đó,
  $a_i$ sẽ được đánh dấu là được chọn.
• Chọn một phần tử
  $a_i$ có
  $1$ phần tử liền kề chưa được chọn (có thể là
  $a_1$,
  $a_n$,
  $a_{i-1}$ hoặc
  $a_{i+1}$ đã được chọn trước đó), điển số của bạn cộng thêm giá trị của phần tử liền kề đó. Sau đó,
  $a_i$ sẽ được đánh dấu là được chọn.
• Chọn một phần tử
  $a_i$ có
  $0$ phần tử liền kề chưa được chọn, khi đó điểm số của bạn cộng thêm
  $0$.

Nhiệm vụ của bạn là tối đa hóa điểm số của mình.

2. Lời giải.

Bài này mình chưa có cách giải chuẩn nên mình sẽ tạm để trống. Ở dưới là code của mình với độ phức tạp là từ

$O(n^2)$ đến

$O(n^3)$, bạn có thể tham khảo.

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ll long long
#define lld long double
#define ull unsigned long long
#define left(a, v) lower_bound(a.begin(), a.end(), v)-a.begin()
#define right(a, v) upper_bound(a.begin(), a.end(), v)-a.begin()
#define print(a) for (auto const& x : a) cout << x << " "; cout << "\n";
#define get_an_ac ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const ll lim = 1000; ll a[lim+5]{0}; lld dp[lim+5][lim+5];
lld dfs(ll l, ll r) {
    lld ans = 0.0; if (l >= r) return 0.0;
    if (dp[l][r] != -1) return dp[l][r];
    for (ll x = l; x <= r; x++) {
        if (a[x] != -1) {
            ll tmp = a[x]; a[x] = -1;
            if (a[x-1] == -1 && a[x+1] != -1) ans = max(ans, dfs(l, x-1)+a[x+1]+dfs(x+1, r));
            if (a[x-1] != -1 && a[x+1] == -1) ans = max(ans, dfs(l, x-1)+a[x-1]+dfs(x+1, r));
            if (a[x-1] != -1 && a[x+1] != -1) ans = max(ans, dfs(l, x-1)+1.0*(a[x-1]+a[x+1])/2+dfs(x+1, r));
            a[x] = tmp;
        }
    } dp[l][r] = ans; return ans;
}
void solve() {
    ll n; cin >> n; a[0] = a[n+1] = -1;
    for (ll x = 1; x <= n; x++) {
        cin >> a[x]; 
        for (ll y = 1; y <= n; y++) dp[x][y] = -1.0;
    } cout << setprecision(1) << fixed << dfs(1, n) << "\n";
}
int main() {
    get_an_ac
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll t; cin >> t; while (t--) solve(); return 0;
}

3. Đánh giá.

Một số người kêu bài này khó, một số người kêu bài này dễ nhưng theo mình, đây là một bài khá hay và không dễ.

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ừ

$6$ đến

$8.75$.

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

• Đề phân hóa mức độ giỏi của thí sinh khá tốt.
• Bài
  $4$ khá hay mặc dù mình chưa giải ra.

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

• Bài
  $3$ không có giới hạn của
  $a_i$ và tại sao lại có subtask
  $1\le n\le {10}^2$? Đến giờ mình vẫn không hiểu tại sao lại có subtask này. Theo mình nếu được chia subtask cho bài
  $3$, mình sẽ chia như sau:
  • Subtask
    $1$
    $(20\mathrm{\%})$:
    $1\le n\le {10}^3;1\le a_i\le {10}^9$.
  • Subtask
    $2$
    $(20\mathrm{\%})$:
    $1\le n\le {10}^5;{10}^9\ge a_1>a_2>...>a_n\ge 1$.
  • Subtask
    $3$
    $(30\mathrm{\%})$:
    $1\le n,a_i\le {10}^5$.
  • Subtask
    $4$
    $(30\mathrm{\%})$:
    $1\le n\le {10}^5;1\le a_i\le {10}^9$.
• Bài
  $4$ thì đề bài, giới hạn và test ví dụ thì mâu thuẫn nhau. Ngoài ra, đề bài rất khó hiểu và dễ gây nhầm lẫn cho thí sinh ở từ xóa. Bài này chia subtask thì có vẻ ổn rồi, nhưng cũng chưa gọi là được lắm. Nếu là mình, mình sẽ chia như sau:
  • Subtask
    $1$
    $(15\mathrm{\%})$:
    $1\le n\le 10$.
  • Subtask
    $2$
    $(15\mathrm{\%})$:
    $a_1<a_2<...<a_n$.
  • Subtask
    $2$
    $(18\mathrm{\%})$:
    $1\le n\le {10}^2$.
  • Subtask
    $3$
    $(22\mathrm{\%})$:
    $1\le n\le {10}^3$.
  • Subtask
    $4$
    $(30\mathrm{\%})$:
    $1\le n\le {10}^6$.
• Cá nhấn mình thì mình muốn
  $2$ bài đâu nên như những bài
  $800$ Codeforces hơn, tricky nhưng cách giải lại dễ đến bất ngờ.

Chỉ vậy thôi, chúc bạn thành công full đề THT Thành phố Đà Nẵng bảng B 2024 nhé.