Ôn tập TS10 & THTB 2025 - Đề 1: Editorial

Thông tin

Sau đây là lời giải của Đề 1 trong chuỗi đề ôn tập TS10 & THTB 2025.

Bạn đọc có thể nộp và chấm bài TẠI ĐÂY

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

• Ôn tập TS10 & THTB 2025 - Đề 1: Editorial
  • Bài 1: Phân tích dữ liệu
    • Lưu ý trường hợp đặc biệt
    • Subtask 1
    • Subtask 2
  • Bài 2: Rèn luyện
    • Mô hình hóa bài toán
    • Subtask 1
    • Subtask 2
  • Bài 3: Sữa bò
    • Subtask 1
    • Subtask 2
  • Bài 4: Cứu trợ
    • Subtask 1
    • Subtask 2

Bài 1: Phân tích dữ liệu

Lưu ý trường hợp đặc biệt

Trong trường hợp

$A_1=A_2=\cdots =A_n$, tồn tại vô số giá trị

$k$ thỏa mãn đề bài.

Subtask 1

Nhận xét

Giá trị

$k$ tối đa có thể đạt được là

$k=max(A_1,A_2,\dots ,A_n)$.

Vì với

$k>max(A_1,A_2,\dots ,A_n)$ thì

$A_{i}modk=A_i$.

Trong subtask này, ta thử từng giá trị

$k$ từ

$2$ đến

$max(A_1,A_2,\dots ,A_n)$, với mỗi giá trị như vậy ta duyệt qua mảng

$A$ để kiểm tra giá trị đó có hợp lệ hay không.

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

$O(max(A_1,A_2,\dots ,A_n)\times n)$.

Code

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

const int N = 1e5;
long long n, ch, mx;
long long A[N+1];

void check() {
    bool flag = 0;
    for (int i = 1; i <= n; i++)
        if (A[i] != A[1])
            flag = 1;

    if(!flag) {
        cout << -2;
        exit(0);
    }
}

bool isOk(int key) {
    for (int i = 1; i <= n; i++) {
        if (A[i] % key != A[1] % key)
            return 0;
    }

    return 1;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> A[i];
        mx = max(mx, A[i]);
    }

    sort(A+1, A+1+n);

    check();
    bool flag = 0;
    for (int i = 2; i <= mx; i++)
        if (isOk(i)) {
            flag = 1;
            cout << i << " ";
        }

    if (!flag) cout << -1;

    return 0;
}

Subtask 2

Ta phân tích yêu cầu đề bài:

$$\begin{array}{rl}& A_{1}modk=A_{2}modk=\cdots =A_{n}modk\\ & \iff \{\begin{array}{l}{A}_{1}modk=A_{2}modk\\ A_{2}modk=A_{3}modk\\ \dots \\ A_{n-1}modk=A_{n}modk\end{array}\\ & \iff \{\begin{array}{l}{A}_{1}modk-A_{2}modk=0\\ A_{2}modk-A_{3}modk=0\\ \dots \\ A_{n-1}modk-A_{n}modk=0\end{array}\\ & \iff \{\begin{array}{l}(A_1-A_2)modk=0\\ (A_2-A_3)modk=0\\ \dots \\ (A_{n-1}-A_n)modk=0\end{array}\end{array}$$

Như vậy,

$k$ chính là ước chung của

$|A_1-A_2|,|A_2-A_3|,\dots ,|A_{n-1}-A_n|$.

Hay nói cách khác,

$k$ cũng là ước của:

$$X=\text{UCLN}(|A_1-A_2|,|A_2-A_3|,\dots ,|A_{n-1}-A_n|)$$

Sau khi tính được giá trị

$X$, ta thực hiện duyệt đến

$\sqrt{X}$ để thu được các giá trị

$k$.

Để in ra

$k$ tăng dần, ta chia thao tác duyệt ước thành

$2$ bước:

• Với
  $k\le \sqrt{X}$, ta đơn giản duyệt từ
  $2$ đến
  $\sqrt{X}$.
• Với
  $k>\sqrt{X}$, ta duyệt các ước
  $d$ của
  $X$ từ
  $\sqrt{X}$ xuống
  $1$, và lấy
  $k=\frac{X}{d}$.

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

$O\left(n\log \right)$.

$\log$ tượng trưng cho độ phức tạp thời gian của lệnh __gcd() của C++.

Code

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

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

bool spec() {
    for (int i = 2; i <= n; i++)
        if (A[i] != A[i-1])
            return 0;

    return 1;
}

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

    if (spec()) {
        cout << -2;
        return 0;
    }

    int g = abs(A[2] - A[1]);
    for (int i = 3; i <= n; i++)
        g = __gcd(g, abs(A[i] - A[i-1]));

    if (g < 2) {
        cout << -1;
        return 0;
    }

    for (int i = 2; i*i <= g; i++)
        if (g % i == 0)
            cout << i << " ";

    for (int i = sqrt(g); i >= 1; i--)
        if (g % i == 0 && g / i != i)
            cout << g/i << " ";

    return 0;
}

Bài 2: Rèn luyện

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

Bài toán thực chất là tìm độ dài đoạn con ngắn nhất có tổng lớn hơn hoặc bằng

$S$.

Subtask 1

Duyệt

$i$ từ

$1$ đến

$n$ để cố định vị trí bắt đầu của một đoạn con. Sau đó, khởi tạo biến

$j=i$, tăng dần biến

$j$ để mở rộng đoạn con bắt đầu tại

$i$.

Đồng thời duy trì một biến tổng

$\text{sum}$ để lưu tổng của đoạn con

$[i,j]$. Nếu

$\text{sum}\ge S$, ta lấy độ dài đoạn

$j-i+1$ để cực tiểu hóa kết quả.

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

$O\left(n^2\right)$

Code

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

const long long N = 1e6;
int n, res = 1e9;
long long A[N+1], req;

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

    for (int i = 1; i <= n; i++) {
        long long sum = 0;
        for (int j = i; j <= n; j++) {
            sum += A[j];
            if (sum >= req) {
                res = min(res, j-i+1);
            }
        }
    }

    cout << res;

    return 0;
}

Subtask 2

Nhận xét

Vì mảng

$A$ dương nên với một đoạn

$[i,j]$ bất kì ta có:

• Nếu tăng
  $j$, tổng đoạn sẽ tăng.
• Nếu tăng
  $i$, tổng đoạn sẽ giảm.

Do đó, có thể áp dụng kỹ thuật hai con trỏ, khéo léo dịch chuyển hai đầu của đoạn để tìm các đoạn có độ dài nhỏ nhất thỏa mãn tổng đạt ít nhất bằng

$S$.

Cụ thể:

• Duyệt
  $j$ tăng dần từ
  $1$ đến
  $n$. Cố định
  $j$ làm đầu mút trái của đoạn con.
• $i$ là đầu mút phải của đoạn con, ban đầu
  $j=1$. Khi ta duyệt
  $j$ tăng dần, là đang mở rộng đoạn, làm tăng tổng. Vì đề bài yêu cầu cực tiểu hóa độ dài đoạn, nên ta tìm cách "co" đoạn lại bằng cách tăng
  $i$ đến khi nào tổng đoạn vẫn lớn hơn hoặc bằng
  $S$.
• Sau thao tác trên ở mỗi vị trí
  $j$, ta được đoạn
  $[i,j]$ ngắn nhất thỏa đề bài.

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

$O\left(n\right)$.

Code

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

const long long N = 1e6;
int n, res = 1e9;
long long A[N+1], req, sum;

int32_t main() {
    cin >> n >> req;

    int i = 1;
    for (int i = 1; i <= n; i++) cin >> A[i];
    for (int j = 1; j <= n; j++) {
        sum += A[j];
        while (sum - A[i] >= req) {
            sum -= A[i];
            i++;
        }

        if (sum >= req)
            res = min(res, j - i + 1);
    }

    if (res == 1e9) res = -1;
    cout << res;

    return 0;
}

Bài 3: Sữa bò

Subtask 1

Đề bài đảm bảo

$T=Ax+By$ với

$x,y\in N$, nghĩa là luôn có cách để con bò đạt lượng sữa đúng bằng

$T$ chỉ với thao tác cho ăn cỏ hoặc cho ăn ngũ cốc.

Vì vậy, chỉ cần in ra

$T$.

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

$O(1)$.

Code

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

int main(){
    int T;
    cin >> T;
    cout << T;

    return 0;
}

Subtask 2

Áp dụng quy hoạch động.

• Định nghĩa:
  • $d{p}_{i,0}$ là khả năng tạo ra lượng sữa
    $i$ mà không cần vắt sữa.
  • $d{p}_{i,1}$ là khả năng tạo ra lượng sữa
    $i$ khi đã vắt sữa

  $d{p}_{i,j}=1$ tức là có thể tạo được lượng sữa i.
  

  $d{p}_{i,j}=0$ tức là không thể tạo được lượng sữa i.

• Công thức:
  • $d{p}_{i,0}=1$ nếu
    $d{p}_{i-A,0}=1$ hoặc
    $d{p}_{i-B,0}=1$

  Nếu đã tạo được lượng sữa

  $i-A$, có thể cho bò ăn thêm cỏ để đạt lượng sữa

  $i$.
  Tương tự với

  $i-B$.

  • $d{p}_{\lfloor \frac{i}{2}\rfloor ,1}=1$ nếu
    $d{p}_{i,0}=1$.

  Nếu đã tạo được lượng sữa

  $i$ mà không cần vắt, ta có thể thực hiện vắt sữa lúc này để đạt lượng sữa

  $\lfloor \frac{i}{2}\rfloor$.

• Kết quả: Giá trị
  $i$ lớn nhất thỏa mãn
  $d{p}_{i,0}=1$ hoặc
  $d{p}_{i,1}=1$.

Cách áp dụng công thức quy hoạch động

Dễ thấy, trong hai công thức ở trên:

• Công thức thứ nhất mô tả rằng giá trị
  $dp$ trước sẽ tác động đến giá trị
  $dp$ sau.
• Trong công thức thứ hai, giá trị
  $dp$ sau lại tác động đến giá trị
  $dp$ trước.

Do đó, rất khó để quy hoạch động bằng cả hai công thức cùng một lúc.

Nhận xét rằng

$d{p}_{i,1}$ chỉ bị tác động bởi

$d{p}_{x,0}$, do đó ta thực hiện tính

$d{p}_{x,0}$ trước bằng công thức quy hoạch động đầu tiên.

Sau đó thực hiện tính sơ bộ

$d{p}_{i,1}$ bằng công thức thứ hai, áp dụng các giá trị

$d{p}_{i,1}$ đã có.

Tuy nhiên, các giá trị

$d{p}_{i,1}$ chỉ đang mô phỏng chuỗi thao tác kết thúc bằng việc vắt sữa.

Do đó ta tiếp tục sử dụng công thức thứ nhất (mô phỏng việc tiếp tục cho bò ăn) để cập nhật

$d{p}_{i,1}$.

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

$O(n)$.

Code

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

const int N = 5e6;
int T, A, B;
bool dp[N+1][2];

int main() {
    cin >> T >> A >> B;
    dp[0][0] = 1;

    for (int i = 1; i <= T; i++) {
        if (i >= A) dp[i][0] |= dp[i - A][0];
        if (i >= B) dp[i][0] |= dp[i - B][0];
        dp[i/2][1] |= dp[i][0];
    }

    for (int i = 1; i <= T; i++) {
        if (i >= A) dp[i][1] |= dp[i - A][1];
        if (i >= B) dp[i][1] |= dp[i - B][1];
    }

    for (int i = T; i >= 0; i--)
        if (dp[i][0] || dp[i][1]) {
            cout << i;
            return 0;
        }

    return 0;
}

Bài 4: Cứu trợ

Subtask 1

Nhận xét

Từ một điểm, ta tìm cách đi đến các điểm tiếp theo (tức là thỏa mãn thứ tự gốc của đề bài) ở vị trí gần đó nhất.

Xem xét điều kiện của subtask 1:

• $y_i=v_i=0$
• $x_i\le x_{i+1}$ và
  $x_1=-1e3,x_A=1e3$
• $u_i\le u_{i+1}$

Điều kiện trên mô tả:

• Các điểm đều nằm trên trục
  $Ox$.
• Các điểm thu thập thông tin được sắp xếp tăng dần theo vị trí. Điểm số
  $1$ và điểm số
  $A$ nằm ở hai điểm ngoài cùng trên trục.
• Các điểm cứu trợ được sắp xếp tăng dần theo vị trí.

Do đó, nếu ta duyệt các điểm từ trái sang phải trên trục

$Ox$, ta cũng đang thực hiện duyệt theo đúng thứ tự thỏa mãn đề bài, đồng thời đảm bảo chi phí di chuyển là nhỏ nhất.

Ta chỉ cần quan tâm tại một tọa độ

$i$ trên trục

$Ox$ có tồn tại điểm nào không, dễ dàng làm được điều này bằng cách sử dụng cấu trúc dữ liệu map.

Hoặc sử dụng mảng thường và tịnh tiến lên

${10}^3$ để lưu các chỉ số trong đoạn

$[-{10}^3,0)$

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

$O(n\log n)$

Thao tác trên map mất

$\log$

Code

#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;

const int N = 1e3;
long long a, b, res;
pll A[N+1], B[N+1];
map<int, bool> mp;

long long dist(pll pra, pll prb) {
    long long x = (pra.fi - prb.fi);
    long long y = (pra.se - prb.se);

    return (x * x) + (y * y);
}

int main() {
    cin >> a >> b;

    for (int i = 1; i <= a; i++) {
        cin >> A[i].fi >> A[i].se;
        if (i != a) mp[A[i].fi] = 1;
    }

    for (int i = 1; i <= b; i++) {
        cin >> B[i].fi >> B[i].se;
        mp[B[i].fi] = 1;
    }

    pll prv = A[1];
    for (int x = -1e3; x <= 1e3; x++) {
        if (mp[x]) {
            res += dist(prv, {x, 0});
            prv = {x, 0};
        }
    }

    res += dist(prv, A[a]);
    cout << res;

    return 0;
}

Subtask 2

Áp dụng quy hoạch động.

• Định nghĩa:

  • $d{p}_{i,j,0}$ là chi phí nhỏ nhất để đi hết
    $i$ điểm thu thập thông tin đầu tiên và
    $j$ điểm cứu trợ đầu tiên, đang dừng lại tại điểm thu thập thông tin thứ
    $i$.
  • $d{p}_{i,j,1}$ là chi phí nhỏ nhất để đi hết
    $i$ điểm thu thập thông tin đầu tiên và
    $j$ điểm cứu trợ đầu tiên, đang dừng lại tại điểm cứu trợ thứ
    $j$.

• Khởi gán:

  • $d{p}_{1,0,0}=0$: Đội cứu trợ xuất phát tại điểm thu thập thông tin số
    $1$.
  • Mọi giá trị
    $dp$ còn lại gán bằng
    $\mathrm{\infty }$.

• Công thức:

  • Với
    $D((a,b),(c,d))$ là chi phí để di chuyển giữa hai điểm có tọa độ
    $(a,b)$ và
    $(c,d)$.
  • $d{p}_{i,j,0}=min(d{p}_{i-1,j,0}+D((x_i,y_i),(x_{i-1},y_{i-1})),d{p}_{i-1,j,1}+D((x_i,y_i),(u_j,v_j)))$
    Để đạt trạng thái
    $(i,j,0)$, tức là kết thúc tại điểm thu thập thông tin thứ
    $i$, trước đó ta có thể ở trạng thái:
    • $(i-1,j,0)$: Kết thúc tại điểm thu thập thông tin thứ
      $i-1$.
    • $(i-1,j,1)$: Kết thúc tại điểm cứu trợ thứ
      $j$.
  • $d{p}_{i,j,1}=min(d{p}_{i,j-1,0}+D((u_j,v_j),(x_i,y_i)),d{p}_{i,j-1,1}+D((u_j,v_j),(u_{j-1},v_{j-1})))$
    Tương tự với trường hợp ở trên.

• Kết quả:

  $d{p}_{A,B,0}$: Đi hết các điểm, và kết thúc tại điểm thu thập thông tin thứ
  $A$.

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

$O(n)$

Code

#include <bits/stdc++.h>
#define pll pair<long long, long long>
#define fi first
#define se second
using namespace std;

const int N = 1e3;
const long long MX = 1e17;
long long a, b, res, dp[N+1][N+1][2];
pll A[N+1], B[N+1];

long long dist(pll pra, pll prb) {
    long long x = (pra.fi - prb.fi);
    long long y = (pra.se - prb.se);

    return (x * x) + (y * y);
}

int main() {
    cin >> a >> b;

    for (int i = 1; i <= a; i++)
        cin >> A[i].fi >> A[i].se;

    for (int i = 1; i <= b; i++) 
        cin >> B[i].fi >> B[i].se;

    for (int i = 0; i <= a; i++)
        for (int j = 0; j <= b; j++)
            dp[i][j][0] = dp[i][j][1] = MX;

    dp[1][0][0] = 0;
    for (int i = 0; i <= a; i++) {
        for (int j = 0; j <= b; j++) {
            if (i > 0)
                dp[i][j][0] = min({ dp[i][j][0],
                                    dp[i - 1][j][0] + dist(A[i - 1], A[i]),
                                    dp[i - 1][j][1] + dist(A[i], B[j])});

            if (j > 0)
                dp[i][j][1] = min({ dp[i][j][1],
                                    dp[i][j - 1][1] + dist(B[j - 1], B[j]),
                                    dp[i][j - 1][0] + dist(A[i], B[j])});
        }
    }

    cout << dp[a][b][0] << endl;
}