# Lời giải đề thi HSG tỉnh lớp 11 tỉnh Hà Tĩnh môn Tin học năm học 2024 - 2025

**Author:**
- **Nguyễn Trọng Hoàng** (Chuyên tin khoá 3 - THPT Chuyên Hà Tĩnh)
- **Đào Nhật Tân** (Chuyên tin khoá 3 - THPT Chuyên Hà Tĩnh)

[Link đề bài](https://www.facebook.com/chtcoder/posts/pfbid02b9DkdPf8KpzLWYztt89jhuP8mUUdyLB4YAndh3WtXiLo2ahAHuUJECXqrhh7bc5El?__cft__[0]=AZWSXlO7iRwqHFfrwPOQH_FTbyuwSWMPSzIQtCXnXdw7dVy0KEGqK5ivXITZch1ML02ceJSZz9CmcNgcP1aPOZSzQ36CuyiABRA7xi8e_nga6QbZw50aa0yT6o9DZx8QS7-ks7g5Gfko9Ls7h0GKnLdsHqUuDW9X6G6dw3pr0P4Y0K_GVJX0A66JZsWIgJbmdSdqI6Mgbm6HZ-Eo5aWwatDF&__tn__=%2CO%2CP-R)
[Link chấm bài CHTOJ](https://oj.thptchuyenhatinh.edu.vn/contest/hsg11_20242025)

## Bài 1: Thừa số nguyên tố
[Link chấm bài](https://oj.thptchuyenhatinh.edu.vn/problem/hsg11_2425_bai1)

### Với $2 \le n \le 10^4, q = 1$
- Duyệt từ $2$ tới $n$ kiểm tra ước nguyên tố nhỏ nhất của mỗi số.
- Do ước nguyên tố là ước nhỏ nhất lớn hơn $1$ nên không cần kiểm tra tính nguyên tố.
- Độ phức tạp thuật toán là $O(n \sqrt n)$.

<details>
<summary>Code C++</summary>

int cnt = 0;
for (int i = 2; i <= n; ++i) {
    int t = i;
    for (int j = 2; j \* j <= i; ++j) {
        if (i % j == 0) {
            t = j;
            break;
        }
    }
    cnt += (t == x);
}

cout << cnt;

</details>

### Với $n, q \le 10^3$
- Gọi $d_i$ là ước nguyên tố nhỏ nhất của $i$.
- Tìm tất cả $d_i$, sau khi tìm được thì lưu vào mảng phân phối $cnt$: với mỗi $d_i$ tăng $cnt(d_i)$ lên $1$x.
- Đáp án của $x_i$ là $$.
- Độ phức tạp thuật toán là $O(n \sqrt n)$.

<details>
<summary>Code C++</summary>

vector<int> cnt(n + 1);
for (int i = 2; i <= n; ++i) {
    int d = i;
    for (int j = 2; j \* j <= i; ++j) {
        if (i % j == 0) {
            d = j;
            break;
        }
    }
    cnt[d]++;
}

while (q--) {
    int x;
    cin >> x;
    cout << (x <= n ? cnt[x] : 0) << \'\n\';
}

</details>

### Với $n, q \le 10^6$
- Đặt $c_i$ là số để kiểm tra xem $i$ đã duyệt chưa.
- Đặt toàn bộ $c_i = 0$.
- Duyệt $i$ từ $1$ đến $n$, mỗi $i$ duyệt tất cả bội $j$ của $i$:
- Nếu $c_j = 0$ thì chắc chắn $i$ là ước nhỏ nhất của $j$ nên đặt $c_j = 1$ và tăng $cnt(i)$ lên $1$.
- Nếu $c_j = 1$ thì bỏ qua.
- Còn lại làm giống với $n, q \le 10^3$.
- Độ phức tạp thuật toán là $O(n\ log\ n)$.

<details>
<summary>Code C++</summary>

vector<int> c(n + 1), cnt(n + 1);

for (int i = 2; i <= n; ++i) {
    for (int j = i; j <= n; j += i) {
        if (!c[j]) {
            cnt[i]++;
            c[j] = 1;
        }
    }
}

while (q--) {
    int x;
    cin >> x;
    cout << (x <= n ? cnt[x] : 0) << \'\n\';
}

</details>

## Bài 2: Dãy tam giác
[Link chấm bài](https://oj.thptchuyenhatinh.edu.vn/problem/hsg11_2425_bai2)
### Với $n \le 20$
- Tìm tất cả dãy con liên tiếp và kiểm tra.
- Độ phức tạp thuật toán là $O(n^5)$.

<details>
<summary>Code C++</summary>

int ans = 0;
for (int i = 0; i < n; ++i) {
    for (int j = i + 2; j < n; ++j) {
        bool c = 1;

        for (int x = i; x <= j && c; ++x) {
            for (int y = x + 1; y <= j && c; ++y) {
                for (int z = y + 1; z <= j && c; ++z) {
                    if (a[x] + a[y] <= a[z] || a[x] + a[z] <= a[y] || a[y] + a[z] <= a[x])
                        c = 0;
                }
            }
        }

        if (c) ans = max(ans, j - i + 1);
    }
}

cout << ans;

</details>

### Với $n \le 10^3$
- Ta thấy với ba số $x, y, z$ mà $x \le y \le z$, dễ thấy $x + z > y$ và $y + z > x$. Vậy chỉ cần xét điều kiện $x + y > z$.
- Như vậy trong một dãy, chỉ cần xét hai số nhỏ nhất $l_1, l_2$ và số lớn nhất $h$; dãy sẽ thỏa mãn nếu $l_1 + l_2 > h$.
- Dễ thấy nếu một dãy thỏa mãn, tất cả dãy con của nó cũng thỏa mãn nên ta có thể sử dụng kĩ thuật hai con trỏ.
- Độ phức tạp thuật toán là $O(n^2)$.

<details>
<summary>Code C++</summary>

bool check(int i, int j) {
    int l1 = 1e9, l2 = 1e9, h = 0;
    cout << i << \' \';
    for (; i <= j; ++i) {
        if (a[i] <= l1) {
            l2 = l1;
            l1 = a[i];
        } else l2 = min(l2, a[i]);

        h = max(h, a[i]);
    }

    return l1 + l2 > h; 
}

int ans = 0, i = 0;
for (int j = 0; j < n; ++j) {
    while (j - i + 1 >= 3 && !check(i, j)) i++;
    if (j - i + 1 >= 3) ans = max(ans, j - i + 1);
}

cout << ans;

</details>

### Với $n \le 10^5$
- Ta có thể tìm $l_1, l_2$ và $r$ bằng CTDL Multiset.
- Độ phức tạp thuật toán là $O(n\ log\ n)$

<details>
<summary>Code C++</summary>

int ans = 0, i = 0;
multiset<int> s;
for (int j = 0; j < n; ++j) {
    s.insert(a[j]);
    while (s.size() >= 3 && \*s.begin() + \*++s.begin() <= \*--s.end()) {
        s.erase(s.find(a[i]));
        i++;
    }

    if (j - i + 1 >= 3) ans = max(ans, j - i + 1);
}

cout << ans;

</details>

### Với $n \le 10^6$ và $a_1 \le a_2 \le \ldots \le a_n$
- Ta thấy $l_1, l_2$ là hai số đầu và $r$ là số cuối của dãy con nên có thể lấy trực tiếp.
- Độ phức tạp thuật toán là $O(n)$.

<details>
<summary>Code C++</summary>

int ans = 0, i = 0;
for (int j = 0; j < n; ++j) {
    while (j - i + 1 >= 3 && a[i] + a[i + 1] <= a[j]) i++;
    if (j - i + 1 >= 3) ans = max(ans, j - i + 1);
}

cout << ans;

</details>

## Bài 3: Dãy ngoặc đúng
[Link chấm bài](https://oj.thptchuyenhatinh.edu.vn/problem/hsg11_2425_bai3)
### Với $S \le 10^6$ và chỉ có một kí tự $?$
- Giả sử dấu `(` là $1$ và dấu `)` là $-1$ và $t_i$ là tổng $i$ số đầu nếu xem các ngoặc là các số trên.
- Ta thấy trong một dãy đúng độ dài $l$ thì $t_i \ge 0$ với mọi $i$ và $t_l = 0$.
- Xét hai dấu `(` và `)` cho dấu `?` và tìm đáp án.
- Độ phức tạp thuật toán là $O(n)$.

<details>
<summary>Code C++</summary>

int get(int f, char c) {
    s[f] = c;
    int d = 0, ans = 0;
    for (int i = 0; i < s.size(); ++i) {
        d += (s[i] == '(' ? 1 : -1);
        ans = max(ans, d);

        if (d < 0) return -1;
    }
    if (d != 0) return -1;
    return ans;
}

int f = find(s.begin(), s.end(), '?') - s.begin();
cout << max(get(f, '('), get(f, ')'));

</details>

### Với $S \le 20$
- Xét tất cả cách điền cho dấu `?`.
- Độ phức tạp thuật toán là $O(2^n \cdot n)$.

<details>
<summary>Code C++</summary>

int f(int i, int d) {
    if (d < 0) return -1;
    if (i == s.size()) return d == 0 ? 0 : -1;

    int x = d, p = 0;

    if (s[i] != ')') {
        int t = f(i + 1, d + 1);
        if (t != -1) {
            p = 1;
            x = max(x, t);
        }
    }

    if (s[i] != '(') {
        int t = f(i + 1, d - 1);
        if (t != -1) {
            p = 1;
            x = max(x, t);
        }
    }

    return p ? x : -1;
}

cout << f(0, 0);

</details>

### Với $S \le 10^3$
- Gọi $dp(i, k)$ là độ sâu lớn nhất nếu $t_i = k$.
- Đặt $dp(0, 0) = 0$ và $dp(0, k) = -1$ với $k \neq 0$.
- Với $i \ge 1$ và $k \le n$ ta có:
- Nếu $S_i =$ `)` hoặc `?` và $dp(i - 1, j - 1) \neq -1$ thì $dp(i, k) = max(dp(i - 1, j - 1), k, dp(i, k))$.
- Nếu $S_i =$ `(` hoặc `?` và $dp(i - 1, j + 1) \neq -1$ thì $dp(i, k) = max(dp(i - 1, j + 1), dp(i, k))$.
- Nếu không có cách điền thì $dp(i, k) = -1$.
- Đáp án là $dp(n, 0)$.
- Độ phức tạp thuật toán là $O(n^2)$.
<details>
<summary>Code C++</summary>

int n = s.size();
s = ' ' + s;

vector<vector<int>> dp(n + 1, vector<int> (n + 1, -1));
dp[0][0] = 0;

for (int i = 1; i <= n; ++i) {
    for (int k = 0; k <= n; ++k) {
        if (s[i] != ')' && k > 0 && dp[i - 1][k - 1] != -1)
            dp[i][k] = max(dp[i - 1][k - 1], k);

        if (s[i] != '(' && k < n && dp[i - 1][k + 1] != -1)
            dp[i][k] = max(dp[i][k], dp[i - 1][k + 1]);
    }
}

cout << dp[n][0];

</details>