Đề THT B - BRVT - 2020: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tin học trẻ bảng B tỉnh Bà Rịa - Vũng Tàu năm học 2019 - 2020.

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)

• Đề THT B - BRVT - 2020: Editorial
  • Bài 1: Tam giác vuông (40 điểm)
    • Tóm tắt đề bài
    • Lời giải
  • Bài 2: Sân bay (30 điểm)
    • Tóm tắt đề bài
    • Lời giải
  • Bài 3: Alibaba mua hàng (30 điểm)
    • Tóm tắt đề bài
    • Lời giải

Bài 1: Tam giác vuông (40 điểm)

Tóm tắt đề bài

Cho số nguyên dương

$p$.

Yêu cầu: Đếm số lượng bộ ba số nguyên dương

$a\le b\le c$ thỏa mãn

$a+b+c=p$ và là độ dài ba cạnh của một tam giác vuông.

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

$p\le {10}^6$.

Lời giải

Các bộ

$(a,b,c)$ thỏa mãn bài toán là các bộ ba Pytago thỏa

$a+b+c=p$.

Theo công thức Euclid, ta có khái niệm bộ ba Pytago nguyên tố là bộ

$(a,b,c)$ trong đó:

• $a=m^2-n^2$
• $b=2mn$
• $c=m^2+n^2$

$m,n$ là các số nguyên tố cùng nhau, nghĩa là

$\mathrm{UCLN}(m,n)=1$, và đúng một trong chúng là số chẵn.

Từ một bộ ba Pytago nguyên tố, ta có thể tạo ra một bộ ba Pytago bằng cách nhân một số nguyên dương

$k$ vào cả

$a,b,c$. Tức là

$(ka,kb,kc)$.

Như vậy, ta có thể duyệt qua

$m$ và

$n$ để thử mọi bộ ba Pytago nguyên tố, sau đó lại kiểm tra xem có một bộ ba Pytago nào có thể được tạo ra thỏa mãn

$ka+kb+kc=p$ không.

Cách duyệt tối ưu

Ta duyệt qua mọi

$n$ từ

$1$ đến

$p$, sau đó ta duyệt

$m$ từ

$n+1$ (vì

$m>n$) và dừng vòng lặp khi

$m^2+n^2>p$ hoặc

$2mn>p$.

Vì hai số

$m,n$ phải khác tính chẵn lẻ, trong vòng lặp ta luôn cộng

$m$ lên

$2$.

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

$O\left(p\sqrt{p}\right)$.

Thực tế, độ phức tạp nhỏ hơn nhiều, nhưng khó tính được chính xác.

Code

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

long long p, res;

int main() {
    cin >> p;

    for (long long n = 1; n <= p; n++)
        for (long long m = n+1; m*m + n*n <= p && 2*m*n <= p; m += 2) {
            if (__gcd(m, n) > 1) continue;

            long long a = m*m - n*n;
            long long b = 2*m*n;
            long long c = m*m + n*n;

            if (a + b + c > p) break;

            if (p % (a + b + c) == 0) res++;
        }

    cout << res;

    return 0;
}

Bài 2: Sân bay (30 điểm)

Tóm tắt đề bài

Có

$n$ người, người thứ

$i$ ở sân bay trong khoảng thời gian từ

$l_i$ đến

$r_i$.

Yêu cầu: Tìm số người lớn nhất trong sân bay ở cùng một thời điểm.

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

$n\le {10}^4$ và

$a_i<b_i<{10}^9$.

Lời giải

Gọi

$f_i$ là số người trong sân bay tại thời điểm

$i$.

Như vậy, nếu người thứ

$i$ ở sân bay từ

$l_i$ đến

$r_i$, ta tăng giá trị của

$f_{l_i},f_{l_i+1},\dots ,f_{r_i}$ lên

$1$.

Tối ưu

Tăng giá trị của

$f_{l_i},f_{l_i+1},\cdots ,f_{r_i}$ nhanh bằng mảng hiệu.

Dễ nhận thấy không thể lưu trữ mảng với

${10}^9$ phần tử.

Nhưng số lượng giá trị

$l_i,r_i$ khác nhau chỉ đạt tối đa

$2n$. Do đó ta dùng kĩ thuật nén số.

Đáp án:

$max(f_1,f_2,\cdots ,f_{{10}^9})$

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

$O(n\log n)$.

Code

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

const int N = 1e4 + 5;
int n, f[2*N], l[N], r[N];
vector <int> vt;

int main(){
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
        vt.push_back(l[i]);
        vt.push_back(r[i]);
    }
    
    ///Nén số
    sort(vt.begin(), vt.end());
    vt.erase(unique(vt.begin(), vt.end()), vt.end());
    for (int i = 1; i <= n; i++){
        l[i] = lower_bound(vt.begin(), vt.end(), l[i]) - vt.begin() + 1;
        r[i] = lower_bound(vt.begin(), vt.end(), r[i]) - vt.begin() + 1;
    }
    
    ///Mảng hiệu
    for (int i = 1; i <= n; i++){
        f[l[i]]++;
        f[r[i] + 1]--;
    }

    int res = 0;
    for (int i = 1; i <= 2*n; i++){
        f[i] = f[i-1] + f[i];
        res = max(res, f[i]);
    }

    cout << res;

    return 0;
}

Bài 3: Alibaba mua hàng (30 điểm)

Tóm tắt đề bài

• Cho
  $n$ loại tiền có mệnh giá là
  $a_i$ khác nhau.
• Cho
  $m$ món hàng với giá tiền của món đồ thứ
  $i$ là
  $b_i$
• Một món hàng có thể được mua nếu có thể dùng các đồng tiền trong
  $n$ loại tiền để tạo ra giá trị đúng bằng
  $b_i$ (mỗi đồng tiền chỉ sử dụng một lần với một món hàng).

Yêu cầu: in ra số lượng món hàng có thể mua được.

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

• $n\le 100$;
• $m\le 10000$;
• $a_i\le 100$;
• $b_i\le 10000$.

Lời giải

Áp dụng quy hoạch động cái túi.

• Định nghĩa:
  $f_{i,j}$ là khả năng tạo ra giá trị
  $j$ nếu chỉ xét
  $i$ đồng tiền đầu tiên.
  • $f_{i,j}=1$: Có thể tạo ra giá trị
    $j$ với
    $i$ đồng tiền đầu tiên.
  • $f_{i,j}=0$: Không thể tạo ra giá trị
    $j$ với
    $i$ đồng tiền đầu tiên.
• Khởi gán:
  $f_{0,0}=1$ (có thể tạo được giá trị
  $0$ bằng cách không lấy đồng nào).
• Công thức:
  $f_{i,j}=max(f_{i-1,j},f_{i-1,j-A_i})$.
  • $f_{i-1,j}=1$: Không cần đồng xu thứ
    $i$ đã có thể tạo được tổng
    $j$.
  • $f_{i-1,j-A_i}=1$: Đã tạo được tổng
    $j-A_i$ mà không cần dùng đồng xu thứ
    $i$, do đó nếu dùng thêm đồng xu thứ
    $i$ ta được tổng
    $j$.

Đáp án: Món hàng thứ i có thể mua được nếu

$f_{n,b_i}=1$.

Code

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

const int N = 105, M = 1e4 + 5;
int n, f[N][M], m, a[N], b[M];

int main(){
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }

    f[0][0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 10000; j++) {
            if (j >= a[i]) {
                f[i][j] = max(f[i-1][j], f[i-1][j - a[i]]);
            }
            else {
                f[i][j] = f[i-1][j];
            }
        }
    }

    int res = 0;
    for (int i = 1; i <= m; i++) {
        if (f[n][b[i]] == 1) {
            res++;
        }
    }

    cout << res;

    return 0;
}