Đề HSG10-11 - BRVT - 2025: Editorial

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.

Chuẩn bị bởi team Logica, thuộc khuôn khổ dự án The Algitect (ALGI Project)

• Đề HSG10-11 - BRVT - 2025: Editorial
  • Bài 1: Đếm số (4 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 2: Tổng số nguyên tố (5 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
    • Subtask 3
  • Bài 3: Đoạn con đẹp (6 điểm)
    • Tóm tắt đề bài
    • Mô hình hóa bài toán
    • Subtask 1
    • Subtask 2
    • Subtask 3
  • Bài 4: Lắp ráp thiết bị (5 điểm)
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2

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

$xmoda=xmodb$.

Dữ liệu đảm bảo:

$1\le n,a,b,\le {10}^{18}$.

Subtasks:

• $75\mathrm{\%}$ số điểm:
  $1\le n,a,b\le {10}^6$.
• $25\mathrm{\%}$ 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)$.

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

Nhận xét

Giả sử ta có:

$$xmoda=xmodb=r(r\in \mathrm{N})$$
Khi đó:

$$(x-r)moda=(x-r)modb)=0$$

Nói cách khác,

$x-r$ là bội của

$\mathrm{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

$\mathrm{BCNN}(a,b)$, ta có

$min(a,b)$ đáp án, đó là:

$$t,t+1,\dots ,t+min(a,b)-1$$

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>n$, vì có đáp án lớn hơn
  $n$.

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>n$ (nếu có,
  $t$ này là bội lớn nhất), có
  $n-t+1$ đáp án:
  
  $$t=\lfloor \frac{n}{\mathrm{BCNN}(a,b)}\rfloor \times \mathrm{BCNN}(a,b)$$
• $t>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
    $\mathrm{BCNN}(a,b)$ thỏa
    $t>0$ và
    $t+min(a,b)-1\le n$:
    
    $$\lfloor \frac{n-min(a,b)+1}{\mathrm{BCNN}(a,b)}\rfloor$$
  • Số lượng
    $r$ (từ
    $0$ đến
    $min(a,b)-1$):
    
    $$min(a,b)$$

Tính nhanh BCNN

Ta có:

$$\mathrm{BCNN}(a,b)=\frac{a\times b}{\mathrm{UCLN}(a,b)}$$
Có thể tính nhanh

$\mathrm{UCLN}(a,b)$ bằng câu lệnh __gcd() có sẵn của C++.

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)+(n-\lfloor \frac{n}{\mathrm{BCNN}(a,b)}\rfloor \times \mathrm{BCNN}(a,b)+1)+\lfloor \frac{n-min(a,b)+1}{\mathrm{BCNN}(a,b)}\rfloor \times [min(a,b)]$$

Độ phức tạp thời gian:

$O(\log min(a,b))$

Độ phức tạp của thuật toán Euclid để tìm BCNN.

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\mathrm{\%}$ số điểm:
  $T=1$ và
  $1\le a,b\le {10}^3$.
• $40\mathrm{\%}$ số điểm:
  $T\le {10}^3$ và
  $1\le a,b\le {10}^4$.
• $40\mathrm{\%}$ 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(\sqrt{a}+\sqrt{a+1}+\cdots +\sqrt{b})$.

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ố để 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(T\times (b-a)+b\log \log b)$.

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$.

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):

• 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(T+b\log \log b)$.

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\mathrm{\%}$ số điểm:
  $1\le T\le 3$ và
  $1\le n\le {10}^5$.
• $25\mathrm{\%}$ số điểm:
  $1\le n\le {10}^5$ và
  $1\le a_i\le 10$.
• $50\mathrm{\%}$ 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

$cn{t}_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(T\times n\log n)$.

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.

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).

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(n+T\times 10)$.

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

Thuật toán

Bài này yêu cầu sử dụng kỹ thuật XOR hashing.

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{array}{r}\underset{cn{t}_{x}mod2=0}{\underbrace{x\oplus x\oplus x\oplus \cdots \oplus x}}=0\\ \underset{cn{t}_{x}mod2=1}{\underbrace{x\oplus x\oplus x\oplus \cdots \oplus x}}=x\end{array}$$

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 \cdots \oplus a_j=(a_1\oplus a_2\oplus \cdots \oplus a_j)\oplus (a_1\oplus a_2\oplus \cdots \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 \cdots \oplus a_j=0$$

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(T+n)$.

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\mathrm{\%}$ số điểm:
  $1\le k\le n\le 20$;
• $75\mathrm{\%}$ 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ị.

Độ phức tạp thời gian theo cách trên:

$O\left(P_n^k\right)$.
Trong đó

$P_n^k$ 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.

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.

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:

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{array}{rl}{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{array}$$

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{array}{rl}{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{array}$$

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_n^k\right)$.

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(f_{i,j-1},f_{i-1,j-1}+|b_i-a_j|)$$
  • $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)$.

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;
}