Đề TS10 - BRVT - 2023: Editorial

Thông tin

Sau đây là lời giải của Kỳ thi Tuyển sinh 10 trường THPT chuyên Lê Quý Đôn tỉnh Bà Rịa - Vũng Tàu năm học 2023 - 2024.

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)

• Đề TS10 - BRVT - 2023: Editorial
  • Bài 1
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 2
    • Tóm tắt đề bài
    • Nhị phân và thập phân
    • Subtask 1
    • Subtask 2
  • Bài 3
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 4
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2

Bài 1

Tóm tắt đề bài

Một quyển sách gồm

$N$ trang. Trong đó trang

$1$ luôn nằm phía bên phải của trang bìa đầu, trang

$N$ luôn nằm ở mặt bên trái của trang bìa cuối của quyển sách.

Sau khi lật trang

$1$ sẽ đến trang

$2,3$, rồi đến

$4,5$, … Ngược lại, nếu lật từ trang

$N$, ta sẽ đến trang

$N-1,N-2$, rồi

$N-3,N-4$, …

Yêu cầu: Cho

$P$, tìm số bước ít nhất để lật đến trang

$P$.

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

$N\le {10}^{18}$ và

$1<P<N$.

Ràng buộc:

• $75\mathrm{\%}$ số điểm tương ứng với
  $1<P<N\le {10}^9$;
• $25\mathrm{\%}$ số điểm tương ứng với
  ${10}^9<P<N\le {10}^{18}$.

Subtask 1

Mô phỏng lại quá trình lật sách, duyệt vòng lặp để lật từ trang

$1$ đến trang

$P$, và từ trang

$N$ đến trang

$P$, kết quả là số lần lật ít hơn trong hai cách lật.

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

$O\left(n\right)$.

Code

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

long long n, p, kq1, kq2;

void lm(){
    long long i;
    for (i = 2; i <= p; i += 2) {
        kq1++;
    }
    
    if (p == n) {
        cout << 0;
        return;
    }
    
    for (i = n - 1; i >= p; i -= 2)
        kq2++;
    
    cout << min(kq1, kq2);
}

int main() {
    cin >> n >> p;
    if (p == 1) cout << 0;
    else lm();
    
    return 0;
}

Subtask 2

Nhận xét

Trừ trang

$1$ và trang

$n$, dễ thấy các trang có tính chất xuất hiện theo cặp:

$$(2,3),(4,5),(6,7),(8,9),\dots$$
Nghĩa là, số bước lật đến trang

$3,5,7,9,\dots$ cũng bằng số bước lật đến trang

$2,4,6,8,\dots$

Để dễ xử lí, sau khi nhập vào

$p$, nếu

$p$ chẵn, ta trừ đi

$1$ để được

$p$ chẵn.

Đáp án:

$min(\frac{p}{2},\frac{n-p}{2})$

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

$O\left(1\right)$.

Code

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

int main() {
    long long n, p;
    
	cin >> n >> p;
	if (p % 2 != 0) {
        p--;
    }

    cout << min(p / 2, (n-p) / 2);
    
    return 0;
}

Bài 2

Tóm tắt đề bài

Cho hai số

$a$ và

$b$ ở hệ nhị phân.

Yêu cầu: Đếm số lượng số chính phương trong đoạn

$[a,b]$.

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

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

Ràng buộc:

• $75\mathrm{\%}$ số điểm tương ứng với
  $1<a<b\le {10}^9$.
• $25\mathrm{\%}$ số điểm tương ứng với
  $1<a<b\le {10}^{18}$.

Nhị phân và thập phân

Important

Để xử lý được bài toán này, bắt buộc cần phải biến đổi

$a$ và

$b$ từ hệ nhị phân sang hệ thập phân.

VD:

${1110}_2={14}_{10}$

Trước tiên, cần nắm được mối quan hệ giữa số nhị phân và số thập phân:

$$x_{n-1}{x}_{n-2}\dots x_1{x}_0=x_0\times 2^0+x_1\times 2^1+\cdots +x_{n-2}\times 2^{n-2}+x_{n-1}\times 2^{n-1}$$

Trong đó, vế trái là số nhị phân bất kỳ, và vế phải là biểu diễn thập phân tương ứng của số nhị phân đã cho.

VD:

${1110}_2=0\times 2^0+1\times 2^1+1\times 2^2+1\times 2^3={14}_{10}$

Lưu ý: Trong hệ nhị phân, các chữ số được đánh số từ

$0$, và từ phải qua trái.

Để tính nhanh

$2^0,2^1,\dots ,2^{n-1}$, ta duyệt theo thứ tự các chữ số của số nhị phân, đồng thời duy trì một biến giá trị

$2^i$. Sau khi duyệt qua một số, ta nhân thêm

$2$ vào giá trị này.

Code

int binToDec(string s) {
    int ret = 0;
    long long k = 1;
    for (int i = s.length() - 1; i >= 0; i--) {
        ret += k * (s[i] - '0');
        k *= 2;
    }
    
    return ret;
}

Subtask 1

Duyệt vòng lặp từ

$a$ đến

$b$ các số chính phương tối đa đến

$b$, và kiểm tra xem số đó có lớn hơn hoặc bằng

$a$ hay không. Nghĩa là duyệt

$i$ từ

$1$, số chính phương tương ứng là

$i\times i$, đến khi

$i\times i>b$ thì dừng, trong lúc đó kiểm tra số

$i\times i$ để thêm vào đáp án.

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

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

Code

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

string s1, s2;
long long a, b;

void string_to_num() {
    long long k = 1;
    for (int i = s1.length() - 1; i >= 0; i--) {
        a += k*(s1[i]-'0');
        k *= 2;
    }

    k = 1;
    for (int i = s2.length() - 1; i >= 0; i--) {
        b += k*(s2[i]-'0');
        k *= 2; 
    }
}

int main() {
    cin >> s1 >> s2;
    string_to_num();
    
    long long res = 0;
    for (long long i = 1; i*i <= b; i++)
        if (i*i >= a)
            res++;
    
    cout << res;
    
    
}

Subtask 2

Tip

Ký hiệu số chính phương là

$k^2$ với

$k\in N$.

Theo bài toán, ta có:

$a\le k^2\le b$

$$\begin{array}{rl}& \iff \sqrt{a}\le k\le \sqrt{b}\\ & \iff \lceil \sqrt{a}\rceil \le k\le \lfloor \sqrt{b}\rfloor \end{array}$$

Như vậy, đáp án của bài toán là:

$$\lfloor \sqrt{b}\rfloor -\lceil \sqrt{a}\rceil +1$$

Lưu ý

Cần sử dụng hàm sqrtl thay cho hàm sqrt để đảm bảo độ chính xác. Hoặc tốt hơn nữa, là kiểm tra lại bằng câu lệnh if sau khi sử dụng hàm để tính căn bậc hai.

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

$O(\log a+\log b)$.

Hàm sqrt hay sqrtl có chi phí thời gian là

$\log$.

Code

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

string s1, s2;
long long a, b;

void string_to_num() {
    long long k = 1;
    for (int i = s1.length() - 1; i >= 0; i--) {
        a += k*(s1[i]-'0');
        k *= 2;
    }

    k = 1;
    for (int i = s2.length() - 1; i >= 0; i--) {
        b += k*(s2[i]-'0');
        k *= 2; 
    }
}

int main() {
	cin >> s1 >> s2;
	string_to_num();
    cout << floor(sqrtl(b)) - ceil(sqrtl(a)) + 1;
	return 0;
}

Bài 3

Tóm tắt đề bài

Có

$N$ học sinh tham gia trò chơi được xếp hàng thành một đường thẳng và được đánh số thứ tự từ

$1$ đến

$N$. Biết không được xếp

$3$ bạn nam cùng đứng kế nhau.

Yêu cầu: Hãy cho biết có bao nhiêu cách xếp hàng thỏa mãn điều kiện trên.

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

$N\le 64$.

Ràng buộc:

• $25\mathrm{\%}$ số test tương ứng với
  $1<N\le 20$.
• $75\mathrm{\%}$ số test tương ứng với
  $20<N\le 64$.

Subtask 1

Quay lui để duyệt các cách chọn hợp lệ và cộng vào đáp án.

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

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

Code

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

long long n, kq;

void backTrack(long long i, long long tmp){
    if (i == n + 1) {
        kq++;
        return;
    }
    
    if (tmp < 2) {
        backTrack(i + 1, tmp + 1);
    }
        
    backTrack(i + 1, 0);
}

int main() {
    cin >> n;
    backTrack(1, 0);
    cout << kq;
    return 0;
}

Subtask 2

Áp dụng quy hoạch động cơ bản. Để dễ thao tác, ta coi học sinh nam là 1 và học sinh nữ là 0

• Định nghĩa:
  $d{p}_i$ là số cách xếp
  $i$ học sinh thỏa yêu cầu đề bài.
• Khởi gán:
  • $d{p}_1=2$ (1 / 0)
  • $d{p}_2=4$ (11 / 00 / 10 / 01)
  • $d{p}_3=7$ (110 / 000 / 100 / 010 / 001 / 101 / 011)
• Công thức:
  $d{p}_i=d{p}_{i-1}+d{p}_{i-2}+d{p}_{i-3}$, trong đó:
  • $d{p}_{i-1}$: Có thể ghép 0 vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.
  • $d{p}_{i-2}$: Có thể ghép 01 vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.
  • $d{p}_{i-3}$: Có thể ghép 011 vào một dãy đã hợp lệ mà chắc chắn vẫn hợp lệ.

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

$O(n)$.

Code

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

long long n, kq, dp[100];

int main() {
    cin >> n;
    
    dp[1] = 2;
    dp[2] = 4;
    dp[3] = 7;
    
    for (int i = 4; i <= n; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
    }
    
    cout << dp[n];
    
    return 0;
}

Bài 4

Tóm tắt đề bài

Hoàng có một chiếc thẻ nhớ ngoài dung lượng

$K$ (Gigabyte - GB) để lưu ảnh. Cho biết thông về số lượng các loại bức ảnh, mỗi loại sẽ có dung lượng

$a_i$ và tính thẩm mỹ

$b_i$. Biết rằng một loại ảnh có thể không được chọn hoặc chọn với số lượng không hạn chế.

Ghi chú: 1GB = 1024MB

Yêu cầu: Cho biết tổng giá trị lớn nhất của tính thẩm mỹ thu được khi chọn các ảnh mà vẫn đảm bảo không vượt quá dung lượng?

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

$2\le N\le 1000$,

$1\le K\le 4$,

$1<a_i\le 1024$ và

$1<b_i\le {10}^9$.

Ràng buộc:

• $50\mathrm{\%}$ số điểm tương ứng với
  $2\le N\le 500$,
  $K\le 2$,
  $a_i\le 1024$,
  $b_i\le 32000$.
• $50\mathrm{\%}$ số điểm tương ứng với
  $2\le N\le 1000$,
  $K\le 4$,
  $a_i\le 1024$,
  $b_i\le {10}^9$.

Subtask 1

Áp dụng quy hoạch động cái túi theo cách cơ bản.

• Định nghĩa:
  $d{p}_{i,j}$ là tính thẩm mỹ lớn nhất khi chọn từ
  $i$ loại ảnh đầu tiên và tổng dung lượng bằng
  $j$.
• Khởi gán:
  $d{p}_{0,0}=0$ (khi không chọn ảnh nào thì tổng thẩm mỹ bằng
  $0$).
• Công thức: Lấy kết quả tốt nhất trong hai trường hợp:
  • $d{p}_{i,j}=d{p}_{i-1,j}$ (không lấy loại ảnh thứ
    $i$, giữ độ thẩm mỹ đạt được với
    $i-1$ loại)
  • $d{p}_{i,j}=max(d{p}_{i-1,j-x\times A_i+x\times B_i})$ với
    $x$ là số lượng ảnh loại
    $i$ ta lấy.

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

$O(n\times k^2)$.

Code

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

const int N = 1e3, K = 4*1024;
int n, k;
long long F[N+1][K+1], A[N+1], B[N+1];

int main() {
	cin >> n >> k;
    k *= 1024;
    
	for (int i = 1; i <= n; i++) {
        cin >> A[i] >> B[i];
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            F[i][j] = F[i-1][j];
            if (j - A[i] >= 0) {
                for (int x = 1; x * A[i] <= j; x++) {
                    F[i][j] = max(F[i][j], F[i-1][j - x*A[i]] + x*B[i]);
                }
            }
        }
    }

    cout << F[n][k];

	return 0;
}

Subtask 2

Nhận xét

Ở bài toán cái túi cụ thể này, ta không cần quan tâm đến ràng buộc về phần tử (ta có thể bỏ các đồ vật không giới hạn).

Do đó, có thể bỏ chiều

$i$ trong công thức quy hoạch động ban đầu.

Áp dụng quy hoạch động cái túi biến thể.

• Định nghĩa:
  $d{p}_j$ là tính thẩm mỹ lớn nhất khi chọn ảnh để tổng dung lượng bằng
  $j$.
• Khởi gán:
  $d{p}_0=0$ (khi không chọn ảnh nào thì tổng thẩm mỹ bằng
  $0$).
• Công thức:
  $d{p}_j=max(d{p}_{j-A_i}+B_i)\mathrm{\forall }{A}_i\le j$ (lấy thêm ảnh thứ
  $i$).

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

$O(n\times k)$.

Code

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

const int N = 1e3, K = 4*1024;
int n, k;
long long F[K+1], A[N+1], B[N+1];

int main() {
    cin >> n >> k;
    k *= 1024;

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

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= k; j++) {
            if (j - A[i] >= 0) {
                F[j] = max(F[j], F[j - A[i]] + B[i]);
            }
        }
    }

    cout << F[k];

    return 0;
}