Đề TS10 - BRVT - 2022: 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 2022 - 2023.

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 - 2022: Editorial
  • Bài 1
    • Tóm tắt đề bài
    • Subtask 1 + 2
    • Subtask 3
  • Bài 2
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
  • Bài 3
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
    • Subtask 3
  • Bài 4
    • Tóm tắt đề bài
    • Subtask 1
    • Subtask 2
    • Subtask 3

Bài 1

Tóm tắt đề bài

Cho ba số nguyên

$a,b,k$.

Yêu cầu: Đếm số lượng số chia hết cho

$k$ trong đoạn

$[a,b]$.

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

$1\le k,a,b\le {10}^{18}$ và

$a\le b$.

Ràng buộc:

• $40\mathrm{\%}$ số điểm ứng với
  $1\le k,a,b\le 32000$;
• $40\mathrm{\%}$ số điểm ứng với
  $1\le k,a,b\le {10}^9$,
  $0\le b-a\le {10}^6$;
• $20\mathrm{\%}$ số điểm ứng với
  $1\le k,a,b\le {10}^{18}$.

Subtask 1 + 2

Duyệt vòng lặp

$i$ từ

$a$ đến

$b$ rồi kiểm tra

$i$ có chia hết cho

$k$ không và tăng kết quả.

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

$O(b-a)$.

Code

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

long long k, a, b, res;

int main() {
    cin >> k >> a >> b;
    for (int i = a; i <= b; i++) {
        if (i % k == 0)
            res++;
    }

    cout << res;
    return 0;
}

Subtask 3

Tip

Các số chia hết cho

$k$ trong khoảng từ

$1$ đến

$n$ có dạng

$k,2k,3k,4k,\dots ,dk$. Trong đó

$d$ là số lớn nhất sao cho

$d\cdot k\le n$ hay

$d\le \frac{n}{k}$.

Mà

$d$ là một số nguyên nên

$d=\lfloor \frac{n}{k}\rfloor$.

Như vậy, ta có thể tính nhanh số lượng số chia hết cho

$k$ trong khoảng từ

$1$ đến

$n$ bằng cách lấy kết quả là:

$\lfloor \frac{n}{k}\rfloor$.

Vậy để giải quyết bài toán trên ta sẽ lấy kết quả:

$$\lfloor \frac{b}{k}\rfloor -\lfloor \frac{a-1}{k}\rfloor$$

Là các số chia hết cho

$k$ từ

$1$ đến

$b$ và loại đi các số chia hết cho

$k$ từ

$1$ đến

$(a-1)$.

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

$O\left(1\right)$.

Code

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

long long k, a, b;

int main() {
    cin >> k >> a >> b;
    cout << b/k - (a-1)/k;
    return 0;
}

Bài 2

Tóm tắt đề bài

Cho hai số

$a$ và

$b$ (

$a<b$), tìm số

$x$ không âm nhỏ nhất để

$\mathrm{UCLN}(a+x,b+x)=b-a$.

Yêu cầu: In ra số

$x$ không âm nhỏ nhất tìm được

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

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

$x\ge 0$.

Subtasks:

• $50\mathrm{\%}$ số điểm:
  $1<a<b\le {10}^6$.
• $50\mathrm{\%}$ số điểm: không có ràng buộc gì thêm.

Subtask 1

Chạy vòng lặp từ giá trị

$0$ đến khi tìm được kết quả

$x$ thỏa mãn điều kiện đề bài.

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

$O(b-a)$.

Code

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

long long a, b;

int main() {
    cin >> a >> b;
    for (int i = 0; ; i++) {
        if (__gcd(a + i, b + i) == b - a) {
            cout << i;
            break;
        }
    }
    
    return 0;
}

Subtask 2

Đối với giới hạn lớn, việc dùng vòng lặp để tìm

$x$ là bất khả thi.

Gọi:

• $u=a-b$

Khi đó:

$amodu=bmodu$ (

$1$).

Đề ra

$\mathrm{UCLN}(a+x,b+x)=u$, từ đó suy ra:

• $(a+x)modu=0$
• $(b+x)modu=0$

Vì tính chất (

$1$), ta chỉ cần đảm bảo một trong hai điều kiện trên. Bài toán trở thành tìm số

$x$ nhỏ nhất sao cho:

$(a+x)modu=0$.

Ta có:

$(a+x)modu=0\to x=(-a)modu$.
Mà

$x\ge 0\to x=(-(amodu)+u)modu=u-(amodu)$

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

$O\left(1\right)$.

Code

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

long long a, b, u;

int main() {
    cin >> a >> b;
    u = b - a;
    cout << u - (a % u);
    return 0;
}

Bài 3

Tóm tắt đề bài

Cho mảng

$a$ gồm

$n$ phần tử và một số nguyên

$k$.

Yêu cầu: Hãy đếm số cặp

$(i,j)$ sao cho

$a_i+a_j=k$

$(1\le i<j\le n)$.

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

$1\le a_i\le {10}^9$,

$2\le n\le {10}^5$ và

$1\le k\le 2\cdot {10}^9$.

Ràng buộc:

• $40\mathrm{\%}$ số điểm tương ứng với
  $2\le n\le {10}^3,1\le a_i\le 32000$ .
• $40\mathrm{\%}$ số điểm tương ứng với
  $2\le n\le {10}^5,1\le a_i\le {10}^6$.
• $20\mathrm{\%}$ số điểm không có ràng buộc gì thêm.

Subtask 1

Ta duyệt qua từng cặp

$(i,j)$ trong mảng

$a$, kiểm tra điều kiện rồi tăng biến đếm.

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

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

Code

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

const int N=1e3;
int n,k,res;
int a[N+5];

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        for (int j = 1; j < i; j++) {
            if (a[i] + a[j] == k) res++;
        }
    }
    
    cout << res;
    
    return 0;
}

Subtask 2

Nhận xét

Vì các phần từ trong mảng nhỏ hơn

${10}^6$ nên nếu

$k>{2.10}^6$ thì đáp án là 0.

Vậy ở subtask này ta chỉ cần giải quyết bài toán với

$k\le {2.10}^6$

Ta cố định từng phần tử

$i$, lúc này ta cần đếm số lượng phần tử

$j$

$(1\le j<i)$ sao cho:

$$a_i+a_j=k\iff a_j=k-a_i$$

Ta có thể xử lý việc này bằng mảng đếm.

Gọi

$d_x$ là số lượng phần tử

$x$ đã xuất hiện (tức là ở vị trí bé hơn

$i$). Vậy với mỗi phần tử

$i$ ta sẽ cộng vào kết quả là

$d_{k-a_i}$.

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

$O(n)$.

Code

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

const int N=1e5,MAXVAL=1e6;
int n, k;
long long res;
int a[N+5], d[MAXVAL*2+5];

int main() {
    cin >> n >> k;
    if (k > 2e6){
        cout << 0;
        return 0;
    }
    
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        if (a[i] <= k) res += d[k-a[i]];
        d[a[i]]++;
    }
    
    cout << res;
    
    return 0;
}

Subtask 3

Vì sử dụng mảng đếm nên nếu phần tử

$a_i$ lớn sẽ dẫn đến tràn mảng. Lúc này ta thay thể mảng đếm bằng cấu trúc dữ liệu map.

Độ phức tạp:

$O(n\log n)$.

Code

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

const int N = 1e5;
int n;
long long res, k;
int a[N+5];
map<long long, int> mp;

int main() {
    cin >> n >> k;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        res += mp[k-a[i]];
        mp[a[i]]++;
    }
    
    cout << res;
    return 0;
}

Bài 4

Tóm tắt đề bài

Cho mảng

$a$ gồm

$n$ phần tử hãy tìm dãy con dài nhất của

$a$ sao cho các phần tử liền kề trong dãy con thỏa mãn các điều kiện sau:

• $0<|i-j|\le 10$
• $|a_j-a_i|>0$
• $|a_j-a_i|$ là một số chính phương.

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

$1\le n\le {10}^5$ và

$1\le a_i\le {10}^9$.

Ràng buộc:

• $20\mathrm{\%}$ số điểm tương ứng với
  $1\le n\le 20$.
• $40\mathrm{\%}$ số điểm tương ứng với
  $1\le n\le {10}^3$.
• $40\mathrm{\%}$ số điểm không có ràng buộc gì.

Subtask 1

Ta sử dụng thuật toán quay lui sinh ra tất cả các dãy con của mảng

$a$, kiểm tra điều kiện rồi lấy đáp án.

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

$O(2^n)$.

Code

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

const int N = 20;
int n, res;
int a[N+5];
vector<int> vct;

bool chinh_phuong(int x) {
    int v = sqrt(x);
    return v*v == x;
}

void back_track(int x) {
    if (x > n) {
        res = max(res, (int)vct.size());
    }
    else {
        for (int i=0; i<=1; i++){
            if (i==1) {
                if (vct.size() > 0) {
                    if (x-vct.back() > 10) continue;
                    if (abs(a[x] - a[vct.back()]) == 0) continue;
                    if (!chinh_phuong(abs(a[x] - a[vct.back()])) ) continue;
                }
                vct.push_back(x);
                back_track(x+1);
                vct.pop_back();
            }
            else back_track(x+1);
        }
    }
}

int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    back_track(1);
    cout<<res;
    return 0;
}

Subtask 2

Sử dụng thuật toán quy hoạch động.

• Định nghĩa:
  $f_i$ là dãy con dài nhất thỏa mã điều kiện kết thúc tại
  $i$.
• Khởi gán:
  $f_i=1$ (dãy con luôn có ít nhất 1 phần tử là
  $i$).

Ta duyệt các cặp

$(i,j)$.

• Công thức:
  $f_i=max(f_j+1)$ nếu
  $(i,j)$ thỏa mãn điều kiện đề bài (thêm
  $a_i$ vào cuối dãy con kết thúc tại
  $j$ tạo ra dãy con mới kết thúc tại
  $i$).

Độ phức tạp:

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

Code

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

const int N = 1e3;
int n, res;
int a[N+5], f[N+5];

bool not_stf(int x) {
    int v = sqrt(x);
    return (x == 0 || v*v != x);
}

int main() {
    cin >> n;
    for (int i=1;i<=n;i++) {
        cin >> a[i];
        f[i] = 1;
        for (int j = 1; j < i; j++){
            if (i-j>10 || not_stf(abs(a[i]-a[j]))) continue;
            f[i] = max(f[i], f[j] + 1);
        }
        res = max(res, f[i]);
    }

    cout << res;
    return 0;
}

Subtask 3

Kế thừa tư tưởng của subtask 2.

Tận dụng điều kiện

$0<|i-j|\le 10$, ta chỉ duyệt

$j$ từ

$i-10$ đến

$i-1$.

Độ phức tạp:

$O(n\times 10)$.

Code

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

const int N = 1e5;
int n, res;
int a[N+5], f[N+5];

bool not_stf(int x) {
    int v = sqrt(x);
    return x==0 || v*v!=x;
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        f[i] = 1;
        for (int j = max(1, i-10); j < i; j++){
            if (not_stf(abs(a[i] - a[j]))) continue;
            f[i] = max(f[i], f[j]+1);
        }
        
        res = max(res, f[i]);
    }

    cout << res;
    return 0;
}