# Đề HSG10-11 - BRVT - 2025: Editorial

>[!Note] Thông tin
>Sau đây là lời giải của Kỳ thi Chọn HSG10-11 tỉnh Bà Rịa - Vũng Tàu năm học 2024 - 2025.
>
>**Thời gian thi:** 08:00 - 11:00 ngày 27/03/2025.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_hsg9_2025).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1: Đếm số (4 điểm)

### Tóm tắt đề bài

Cho ba số nguyên dương $n, a, b$.

**Yêu cầu:** Đếm số lượng số nguyên $x \in [1, n]$ thỏa mãn $x \bmod a = x\bmod b$.

**Dữ liệu đảm bảo:** $1 \le n, a, b, \le 10^{18}$.

**Subtasks:**
- $75\%$ số điểm: $1 \le n, a, b \le 10^6$.
- $25\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1

Duyệt qua từng số nguyên $x \in [1, n]$, nếu $x$ thỏa điều kiện, ta tăng đáp án lên $1$.

**Độ phức tạp thời gian:** $O \left( n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std
    
long long n, a, b, res;

int main() {
    cin >> n >> a >> b;
    for (long long i = 1; i <= n; i++)
        if (i % a == i % b)
            res++;

    cout << res;

    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Giả sử ta có:
> $$
> x \bmod a = x \bmod b = r \; (r \in \operatorname{N})
> $$
> Khi đó:
> $$
> (x - r) \bmod a = (x - r) \bmod b) = 0
> $$

Nói cách khác, ==$x - r$ là bội của $\operatorname{BCNN}(a, b)$== với $r \in [0, \min(a, b) - 1]$.

Hay tương ứng với mỗi bội $t$ của $\operatorname{BCNN}(a, b)$, ta có $\min(a, b)$ đáp án, đó là:
$$
t, t + 1, \dots, t + \min(a, b) - 1
$$

>[!Caution] Cảnh báo
> Tuy nhiên, điều này không đúng với:
> - $t = 0$, vì không tính đáp án $0$.
> - $t + \min(a, b) - 1 \gt n$, vì có đáp án lớn hơn $n$.
> :::danger
> Chúng ta cần **xét riêng hai trường hợp** bội $t$ nhỏ nhất và lớn nhất trong khoảng $n$
> :::

Ta xét riêng ba trường hợp:
- $t = 0$ (bội nhỏ nhất), có $\min(a, b) - 1$ đáp án.
- $t + \min(a, b) - 1 \gt n$ (nếu có, $t$ này là bội lớn nhất), có $n - t + 1$ đáp án:
$$
t = \left \lfloor \frac {n} {\operatorname{BCNN}(a, b)} \right \rfloor \times \operatorname{BCNN}(a, b)
$$
- $t \gt 0$ và $t + \min(a, b) - 1 \le n$, số lượng đáp án là số lượng bội $t$ nhân cho số lượng $r$
- Số lượng bội $t$ của $\operatorname{BCNN}(a, b)$ thỏa $t \gt 0$ và $t + \min(a, b) - 1 \le n$:
$$
\left \lfloor \frac {n - \min(a, b) + 1} {\operatorname{BCNN}(a, b)} \right \rfloor
$$
- Số lượng $r$ (từ $0$ đến $\min(a, b) - 1$):
$$
\min(a, b)
$$

>[!Tip] Tính nhanh BCNN
> Ta có:
> $$
> \operatorname{BCNN}(a, b) = \frac {a \times b} {\operatorname{UCLN}(a, b)}
> $$
> Có thể tính nhanh $\operatorname{UCLN}(a, b)$ bằng câu lệnh `__gcd()` có sẵn của C++.
> :::danger
> **Lưu ý:** Với giới hạn dữ liệu lớn, nếu cứ mặc kệ mà tính BCNN, giá trị có thể lên đến $10^{36}$, dẫn đến tràn số.
>
> Do đó ta cần xử lý khéo bằng cách **dừng nếu nhận thấy số quá lớn**!
> :::

**Đáp án:**
$$
(\min(a, b) - 1) + \left( n - \left \lfloor \frac {n} {\operatorname{BCNN}(a, b)} \right \rfloor \times \operatorname{BCNN}(a, b) + 1 \right) + \left \lfloor \frac {n - \min(a, b) + 1} {\operatorname{BCNN}(a, b)} \right \rfloor \times \left[ \min(a, b) \right]
$$

**Độ phức tạp thời gian:** $O \left( \log \min(a, b) \right)$
> Độ phức tạp của thuật toán Euclid để tìm BCNN.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

long long n, a, b;

long long __lcm(long long x, long long y) {
    long long z = x / __gcd(x, y);
    if (z > n / y) return n + 1;
    return (z * y);
}

int main() {
    cin >> n >> a >> b;
    long long t = __lcm(a, b);

    if (a > b) swap(a, b);

    long long res = min(n, (a - 1)) + ((max(0LL, n - a + 1) / t) * a);
    if ((n / t) * t > 0 && (n / t) * t + a - 1 > n)
        res += (n - (n / t) * t + 1);

    cout << res;

    return 0;
}

:::

## Bài 2: Tổng số nguyên tố (5 điểm)

### Tóm tắt đề bài

Cho $T$ truy vấn gồm hai số nguyên $a, b$.

**Yêu cầu:** Với mỗi $a, b$ tính tổng các số nguyên tố trong đoạn $[a, b]$.

**Dữ liệu đảm bảo:** $1 \le T, a, b \le 10^5$.

**Subtasks:**
- $20\%$ số điểm: $T = 1$ và $1 \le a, b \le 10^3$.
- $40\%$ số điểm: $T \le 10^3$ và $1 \le a, b \le 10^4$.
- $40\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1

Duyệt qua từng số $x$ trong đoạn $[a, b]$, kiểm tra tính nguyên tố của $x$ bằng cách duyệt đến $\sqrt x$ để tìm ước số của $x$. Nếu $x$ là số nguyên tố, ta cộng thêm vào đáp án $x$.

**Độ phức tạp thời gian:** $O \left( \sqrt a + \sqrt{a + 1} + \dots + \sqrt b \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

int t, a, b;

bool isPrime(int num) {
    if (num < 2) return 0;

    for (int i = 2; i*i <= num; i++)
        if (num % i == 0)
            return 0;

    return 1;
}

int main() {
    cin >> t;
    while (t--) {
        cin >> a >> b;
        int res = 0;

        for (int i = a; i <= b; i++)
            if (isPrime(i))
                res += i;

        cout << res << "\n";
    }

    return 0;
}

:::

### Subtask 2

Kế thừa tư tưởng từ subtask trước, tuy nhiên ta cần cải tiến việc kiểm tra tính nguyên tố của số $x$.

Nhận thấy $a, b \le 10^4$, ta có thể [**sàng số nguyên tố**](https://blog.28tech.com.vn/sang-so-nguyen-to) để kiểm tra trước tính nguyên tố của tất cả các số cần kiểm tra.

**Độ phức tạp thời gian:** $O \left( T \times (b - a) + b \log \log b \right)$.
>Duyệt qua đoạn $[a, b]$: $b - a$.
>Sàng số nguyên tố đến cận trên là $b$: $b \log \log b$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int MX = 1e4;
int t, a, b;
bool E[MX+1];

void sieve() {
    E[0] = E[1] = 1;
    for (int i = 2; i*i <= MX; i++)
        if (!E[i])
            for (int j = i*i; j <= MX; j += i)
                E[j] = 1;
}

int main() {
    sieve();

    cin >> t;
    while (t--) {
        cin >> a >> b;
        int res = 0;

        for (int i = a; i <= b; i++)
            if (!E[i])
                res += i;

        cout << res << "\n";
    }

    return 0;
}

:::

### Subtask 3

Kế thừa tư tưởng từ subtask trước, tuy nhiên ta cần cải tiến việc duyệt qua đoạn để tính tổng các số nguyên tố. Thay vào đó, ta có thể dùng [**mảng tiền tố (prefix sum)**](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md):
- Gọi $S_r$ là tổng các số nguyên tố nhỏ hơn hoặc bằng $r$.
- Khi đó tổng các số nguyên tố trong đoạn $[l, r]$ là: $S_r - S_{l-1}$

**Độ phức tạp thời gian:** $O \left( T + b \log \log b \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int MX = 1e5;
int t, a, b, S[MX+1];
bool E[MX+1];

void sieve() {
    E[0] = E[1] = 1;
    for (int i = 2; i <= MX; i++) 
        if (!E[i])
            for (int j = i*i; j <= MX; j += i)
                E[j] = 1;
}

int main() {
    sieve();
    for (int i = 1; i <= MX; i++) {
        S[i] = S[i-1];
        if (!E[i])
            S[i] += i;
    }

    cin >> t;
    while (t--) {
        cin >> a >> b;
        cout << S[b] - S[a-1] << "\n";
    }

    return 0;
}

:::

## Bài 3: Đoạn con đẹp (6 điểm)

### Tóm tắt đề bài

Cho dãy số nguyên dương $a_1, a_2, \dots, a_n$.

$S_{i, j}$ là dãy gồm các số liên tiếp $a_i, a_{i+1}, \dots, a_j$. Đoạn con này là ==đoạn con đẹp== nếu:
- ==$| j - i + 1 |$== là số chẵn.
- Có thể xáo trộn vị trí của các số trong đoạn để tạo thành ==palindrome==.

**Yêu cầu:** Cho $T$ truy vấn $i, j$, với mỗi truy vấn kiểm tra xem $S_{i, j}$ có đẹp không.

**Dữ liệu đảm bảo:** $1 \le n, T \le 10^6$ và $1 \le a_i \le 10^8$.

**Subtask:**
- $25\%$ số điểm: $1 \le T \le 3$ và $1 \le n \le 10^5$.
- $25\%$ số điểm: $1 \le n \le 10^5$ và $1 \le a_i \le 10$.
- $50\%$ số điểm: Không có ràng buộc gì thêm.

### Mô hình hóa bài toán

Bài toán thực chất yêu cầu kiểm tra ==trong đoạn $[i, j]$ có giá trị nào xuất hiện lẻ lần== không.

### Subtask 1

Gọi $cnt_i$ là số lần xuất hiện của giá trị $i$. Để duy trì $cnt$, ta có thể sử dụng cấu trúc dữ liệu `map` được cung cấp trong C++ STL.

Với mỗi truy vấn, duyệt từ $i$ đến $j$ để cập nhật số lần xuất hiện của các giá trị.

Cuối cùng, kiểm tra xem có giá trị nào xuất hiện lẻ lần hay không.

**Độ phức tạp thời gian:** $O\left( T \times n \log n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int t, n, A[N+1];

bool check(int l, int r) {
    map<int, int> mp;
    for (int i = l; i <= r; i++)
        mp[A[i]]++;

    for (int i = l; i <= r; i++)
        if (mp[A[i]] % 2 != 0)
            return 0;

    return 1;
}

int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> A[i];

    while (t--) {
        int l, r;
        cin >> l >> r;

        if (check(l, r)) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

:::

### Subtask 2

Kế thừa tư tưởng từ subtask trước.

>[!Tip] Nhận xét
>- Có quá nhiều truy vấn, cần cải tiến việc tính số lần xuất hiện của các giá trị.
>- Lợi dụng đề cho $a_i \le 10$, ta có thể sử dụng [mảng cộng dồn (prefix sum)](https://wiki.vnoi.info/algo/data-structures/prefix-sum-and-difference-array.md).

Gọi $S_{x, i}$ là số lần xuất hiện của giá trị $x$ từ $1$ đến $i$.

Với mỗi truy vấn $(i, j)$, ta duyệt qua các giá trị $x$, kiểm tra số lần xuất hiện của $x$ trong đoạn trên là $S_{x, j} - S_{x, i-1}$ có thỏa mãn hay không.

**Độ phức tạp thời gian:** $O\left( n + T \times 10 \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5;
int t, n, A[N+1], S[11][N+1] ;

bool check(int l, int r) {
    for (int x = 1; x <= 10; x++)
        if ((S[x][r] - S[x][l-1]) % 2 != 0)
            return 0;

    return 1;
}

int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int x = 1; x <= 10; x++)
        for (int i = 1; i <= n; i++) {
            S[x][i] = S[x][i-1];
            if (A[i] == x) S[x][i]++;
        }

    while (t--) {
        int l, r;
        cin >> l >> r;

        if (check(l, r)) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

:::

### Subtask 3

>[!Note] Thuật toán
> Bài này yêu cầu sử dụng kỹ thuật [**XOR hashing**](https://codeforces.com/blog/entry/85900).
>
> Sau đây, lời giải sẽ sử dụng ký hiệu $\oplus$ thay cho phép XOR.

Ta có thể khai thác tính chất của phép XOR:
$$
\begin{flalign}
\underbrace{x \oplus x \oplus x \oplus \dots \oplus x}_{cnt_x \bmod 2 = 0} = 0 \\
\underbrace{x \oplus x \oplus x \oplus \dots \oplus x}_{cnt_x \bmod 2 = 1} = x
\end{flalign}
$$

Ngoài ra, khi ta cần lấy tổng XOR của một đoạn $[i, j]$, ta có:
$$
a_i \oplus a_{i+1} \oplus \dots \oplus a_j = (a_1 \oplus a_2 \oplus \dots \oplus a_j) \oplus (a_1 \oplus a_2 \oplus \dots \oplus a_{i-1})
$$

Một đoạn $[i, j]$ ==có thể== gồm toàn các giá trị xuất hiện chẵn lần nếu như
$$
a_i \oplus a_{i+1} \oplus \dots \oplus a_j = 0
$$

:::danger
**Lưu ý:** Thuật toán trên không **luôn luôn đúng**, vì có thể xảy ra **collision** (nói đơn giản là trùng giá trị).

**Ví dụ:** $(2 \oplus 5 = 7) \Rightarrow 2 \oplus 5 \oplus 7 = 7 \oplus 7 = 0$.

Để **hạn chế collision**, ta kết hợp **hashing**, nghĩa là gán mỗi giá trị $x$ thành một số ngẫu nhiên. Bạn đọc nên tìm hiểu thêm qua bài viết ở trên.

:::

**Độ phức tạp thời gian:** $O\left( T + n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

mt19937_64 rng(time(0));

const int N = 1e6;
int t, n, A[N+1], S[N+1];
map<int, int> val;

int main() {
    cin >> n >> t;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        if (!val.count(A[i])) val[A[i]] = rng();
        A[i] = val[A[i]];
    }

    for (int i = 1; i <= n; i++)
        S[i] = S[i-1] ^ A[i];

    while (t--) {
        int l, r;
        cin >> l >> r;

        if ((S[r] ^ S[l-1]) == 0) cout << "YES\n";
        else cout << "NO\n";
    }

    return 0;
}

:::

## Bài 4: Lắp ráp thiết bị (5 điểm)

### Tóm tắt đề bài

Cho $n$ bộ nguồn với công suất lần lượt là $p_1, p_2, \dots, p_n$.

Cho $k$ thiết bị cần mức công suất lần lượt là $t_1, t_2, \dots, t_n$.

Nếu thiết bị $i$ được gắn với bộ nguồn $j$ thì giá trị $| p_i - t_j |$ được gọi là độ gây hại của thiết bị này.

**Yêu cầu:** Chọn ra $k$ bộ nguồn và ghép với $k$ thiết bị sao cho tổng độ gây hại là nhỏ nhất.

**Dữ liệu đảm bảo:**
- $1 \le k \le n \le 10^3$;
- $1 \le t_i \le 10^2$;
- $1 \le p_j \le 10^2$.

**Subtask:**
- $25\%$ số điểm: $1 \le k \le n \le 20$;
- $75\%$ số điểm: Không có ràng buộc gì thêm.

### Subtask 1

Áp dụng thuật toán quay lui, tạo từng bộ $k$ trong $n$ bộ nguồn rồi lại ghép với $k$ thiết bị.

::: danger

**Độ phức tạp thời gian theo cách trên:** $O\left(P^k_n\right)$.
Trong đó $P^k_n$ là chỉnh hợp chập $k$ của $n$ có công thức là $\frac{n!}{(n-k)!}$

Với độ phức tạp như trên ta chưa thể lấy được trọn điểm của subtask này.
:::

>[!Tip] Nhận xét
> Với mỗi cặp bộ nguồn $(i,j)$ thỏa $t_j \ge t_i$ và mỗi cặp thiết bị $(u,v)$ thỏa $p_u \le p_v$, ta ==luôn ghép thiết bị $i$ với bộ nguồn $u$ và thiết bị $j$ với bộ nguồn $v$== để cực tiểu hóa **độ gây hại**.

>[!Important] Giải thích tính đúng đắn của nhận xét trên
> Ta có **độ gây hại** của hai thiết bị lần lượt là:
>- $S_1 = |t_i - p_u| + |t_j - p_v|$
>- $S_2 = |t_i - p_v| + |t_j - p_u|$
>
>Ta xét hiệu của $S_1$ và $S_2$:
>$$
>S_2 - S_1 =(|t_i - p_v| + |t_j - p_u|) - (|t_i -p_u| + |t_j - p_v|)
>$$
>Do $t_i \le t_j$ và $p_u \le p_v$, nên ta chỉ xét hai trường hợp:
>:::info
>**Trường hợp 1: $t_i \le p_u \le p_v \le t_j$**
>- Khi đó, ta có:
> - $S_1 = p_u - t_i + t_j - p_v$
> - $S_2 = p_v - t_i + t_j - p_u$
>- Vậy hiệu của $S_1$ và $S_2$ là:
>$$
>\begin{flalign}
>S_2 - S_1 &= (p_v - t_i + t_j - p_u) - (p_u - t_i + t_j - p_v) \\
>&= 2(p_v - p_u) \ge 0 \\
>\Rightarrow S_1 \le S_2
>\end{flalign}
>$$
>:::
>:::info
>**Trường hợp 2: $p_u \le t_i \le t_j \le p_v$**
>- Khi đó,ta có:
> - $S_1 = t_i - p_u + p_v - t_j$
> - $S_2 = p_v - t_i + t_j - p_u$
>
>- Vậy hiệu của $S_1$ và $S_2$ là:
>$$
>\begin{flalign}
>S_2 - S_1 &= (p_v - t_i + t_j - p_u) - (t_i - p_u + p_v - t_j) \\
>&= 2(t_j - t_i) \ge 0 \\
>\Rightarrow S_1 \le S_2
>\end{flalign}
>$$
>:::
>:::success
>Vậy nhận xét trên ==đúng trong mọi trường hợp==.
>:::

Với nhận xét trên, ta có thể giải bài toán này như sau:
- Sắp xếp các giá trị của thiết bị và bộ nguồn theo giá trị tăng dần.
- Nếu thiết bị $i$ ghép với bộ nguồn $u$ thì ta luôn ghép thiết bị $j$ $(i \le j \le k)$ với bộ nguồn $v$ $(u \le v \le n)$.
> Nếu coi $i, j$ và $u, v$ nằm trên hai đường thẳng, việc ghép là nối hai điểm lại với nhau, thì sẽ không có đoạn thẳng nào cắt nhau.

**Độ phức tạp thời gian:** $O \left( C^k_n \right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3, MX = 1e18;
int res = MX, n, k, P[N+1], T[N+1];

void backTrack(int id, int last, int cost) {
    if (cost > res) return;
    if (id > k) {
        res = min(res, cost);
        return;
    }

    for (int i = last + 1; i <= n; i++)
        backTrack(id+1, i, cost + abs(P[i] - T[id]));
}

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> P[i];
    for (int i = 1; i <= k; i++) cin >> T[i];

    sort(P+1, P+1+n);
    sort(T+1, T+1+k);

    backTrack(1, 0, 0);
    cout << res;
    
    return 0;
}

:::

### Subtask 2

Kế thừa tư tưởng của subtask trước, nhưng ta áp dụng ==quy hoạch động==.
- **Định nghĩa:** ==$f_{i,j}$== là tổng độ gây hại nhỏ nhất khi xét $j$ bộ nguồn đầu tiên và đã ghép nối được cho $i$ thiết bị đầu tiên.
- **Khởi gán:** ==$f_{0,j}=0$ $(0 \le j \le n$)== vì để ghép nối $0$ thiết bị thì độ gây hại luôn là $0$.
- **Công thức:**
$$
f_{i,j} = \min\left(f_{i,j-1},f_{i-1,j-1}+|b_i - a_j| \right)
$$
- $f_{i,j} = f_{i,j-1}$ khi không sử dụng bộ nguồn $j$
- $f_{i,j} = f_{i-1,j-1} + |b_i - a_j|$ khi thiết bị $i$ được ghép với bộ nguồn $j$.

**Độ phức tạp thời gian:** $O\left(nk\right)$.

:::success
:::spoiler Code

#include <bits/stdc++.h>
using namespace std;

const int N = 1e3;
int n, m, k;
int p[N+5], t[N+5], f[N+5][N+5];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    
    for (int i = 1; i <= k; i++) {
        cin >> t[i];
    }

    sort(p+1, p+1+n);
    sort(t+1, t+1+k);

    //60 ~ INF
    for (int i = 0; i <= k; i++)
        for (int j = 0; j <= n; j++)
            f[i][j] = 1e9;
    
    for (int i = 0; i <= n; i++){
        f[0][i] = 0;
    }

    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            f[i][j] = min(f[i][j-1], f[i-1][j-1] + abs(t[i] - p[j]));
        }
    }

    cout << f[k][n];
    
    return 0;
}

:::