---
title: Lời giải tham khảo đề thi tuyển sinh vào lớp 10 trường PTNK 2023-2024 môn Tin Học
---

# Lời giải tham khảo đề thi tuyển sinh vào lớp 10 trường PTNK 2023-2024 môn Tin Học

-----

###### ✍️ Author:  [I2225 PTNK](https://www.facebook.com/ptnk.i2225)
###### 📋 Content:

[TOC]

-----

## Bài 1
- **Tóm tắt đề:**
- Cho mảng $A$ gồm $N$ phần tử và mảng $B$ gồm $M$ phần tử. Hãy tìm độ dài lớn nhất của mảng được ghép bởi mảng tiền tố của $A$ và hậu tố của mảng $B$ sao cho mảng đó **không giảm**.
- Giới hạn:
- $1 \le N,M \le 10^5$
- $0 \le |A_i|,|B_i| \le 10^9$
- **Lời giải:**
- Ta nhận thấy là ta chỉ quan tâm đoạn tiền tố dài nhất của mảng $A$ và hậu tố dài nhất của mảng $B$ mà không giảm dần vì nếu không thì khi ta ghép lại nó sẽ không thỏa mãn yêu cầu đề bài. Gọi vị trí $x$ là vị trí cuối cùng mà tiền tố của mảng $A$ không giảm dần, vị trí $y$ là vị trí cuối cùng mà hậu tố của mảng $B$ không giảm dần.
- Sau khi tìm được vị trí $x$ và $y$ xong thì ta sẽ xét từng phần tử của tiền tố mảng $A$ và xem ta có thể nối như thế nào để mảng tạo được dài nhất. Việc ta kiểm tra xem ta có thể nối ở đâu ta có thể xét lại từng phần tử mảng B nhưng nó lại không tối ưu. Vì thế, ta có thể sử dụng hai con trỏ cho việc này.
- Từ đó, ta sẽ có thuật toán như thế này:
- Tìm vị trí cuối cùng mà tiền tố của A và hậu tố của B không giảm dần.
- Xét các phần tử $i$ từ $1$ đến $x$ và song song duy trì một con trỏ $j$ để xem là vị trí nào là vị trí mà ta có thể nối tiền tố và hậu tố lại với nhau để được kết quả lớn nhất.
- Ta thấy là ta sẽ đi qua mảng $A$ một lần và mảng $B$ một lần tìm $x$ và $y$ rồi đi qua mảng $A$ và mảng $B$ một lần để tìm đáp án nên độ phúc tạp sẽ là $O(N+M)$.

:::spoiler **Code mẫu:**

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

const int N = 2e5 + 1;
int a[N], b[N];

int main(){
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    freopen("MARBLE.INP", "r", stdin);
    freopen("MARBLE.OUT", "w", stdout);
    
    int n; cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> a[i];
    
    int m; cin >> m;
    for(int i = 1; i <= m; ++i)
        cin >> b[i];

    int x = n , y = 0;

    for(int i = 2; i <= n; ++i){
        if(a[i] < a[i - 1]){
            x = i - 1;
            break;
        }
    }

    for(int i = m - 1; i > 0; --i){
        if(b[i] > b[i + 1]){
            y = i + 1;
            break;
        }
    }

    int j = y, ans = 0;
    bool flag = 0;
    for(int i = 1; i <= x; ++i){
        while(a[i] > b[j]){
            ++j;
            if(j > m){
                flag = 1;
                break; // nếu như j > m rồi thì không cần xét nữa
            }
        }
        if(flag) break;
        ans = max(ans, i + m - j + 1);
    }

    cout << ans;
}

:::
## Bài 2
- **Tóm tắt đề:**
- Cho một bảng có kích thước $N*M$ và $4*K$ điểm phân biệt trên bảng đó. Vậy có bao nhiêu cách cắt bảng này theo **một đường ngang** và **một đường dọc** sao cho 4 phần được chia ra mỗi phần đều có $K$ điểm?
- Giới hạn:
- $1\le N,M \le 10^5$
- $1 \le x_i \le N$
- $1 \le y_i \le M$

- **Lời giải:**
- Bài này với $N,M \le 10^3$ thì ta có thể giải được bằng mảng cộng dồn cơ bản. Nhưng giới hạn $N,M \le 10^5$ thì ta phải suy nghĩ theo hướng khác. Với bài này, ta sẽ xét đường cắt dọc riêng và đường cắt ngang riêng.
- Ta sẽ xét đường cắt dọc trước. Hiển nhiên, để mà có thể cắt 2 đường ngang dọc và được $4$ phần có $K$ điểm thì đường cắt dọc phải chia bảng ra hai phần có $2*K$ điểm. Để biết có bao nhiêu vị trí thỏa mản thì ta có thể sắp xếp theo trục $x$ là nhận xét là các đường dọc giữa điểm thứ $2*K$ và $2*K+1$ sẽ là vị trí cắt thỏa mãn. Nên số lượng vị trí thỏa mãn sẽ là $A_{2*K+1}-A_{2*K}$.
- Sau khi cắt bảng thành 2 phần riêng biệt thì ta sẽ xử lý từng phần riêng. Ta thấy là nếu ta cắt phần thứ nhất trong khoảng $[a,b]$ rồi cắt thành phần thứ hai trong khoảng $[c,d]$ sẽ chia đều các điểm thì số vị trí cắt đường ngang thỏa mãn sẽ là $[a,b] \cap [c,d]$.
- Thì bây giờ việc của mình là xác định $[a,b]$ và $[c,d]$ thì đó là bài toán ta đã làm với đường cắt dọc nhưng bây giờ sắp xếp theo trục $y$. Cuối cùng, ta chỉ cần tìm phần giao của hai khoảng thôi.
- Để tìm phần giao của hai tập thì ta sẽ có thể dùng công thức này: $max(0,min(b,d)-max(a,c))$
- Để tìm đáp án đề bài thì ta sẽ nhân đáp án của hai bước trên lại với nhau.
- Do ta sắp xếp $4*K$ điểm nên độ phức tạp cuối cùng nằm trong khoảng $O(K \log K)$.

:::spoiler **Code mẫu:**

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e6+1;

struct Point {
    int x, y;
};

bool cmpX(Point a, Point b) {
    return a.x < b.x;
}

bool cmpY(Point a, Point b) {
    return a.y < b.y;
}

ll intersection(ll a, ll b, ll c, ll d) {
    return max(0ll, min(b, d) - max(a, c));
}

Point A[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("CAKE.INP", "r", stdin);
    freopen("CAKE.OUT", "w", stdout);

    int n, m, k;
    cin >> n >> m >> k;
    for(int i = 1; i <= 4*k; ++i) {
        int x, y;
        cin >> x >> y;
        A[i] = {x, y};
    }

    sort(A + 1, A + 4*k + 1, cmpX);
    ll a = A[2*k + 1].x - A[2*k].x;
    
    sort(A + 1, A + 2*k + 1, cmpY);
    sort(A + 2*k + 1, A + 4*k + 1, cmpY);
    ll b = intersection(A[k].y, A[k + 1].y, A[3*k].y, A[3*k + 1].y);
    
    cout << a * b;
}

:::
## Bài 3
- **Tóm tắt đề**
- Cho mảng $A$ gồm $N$ phần tử và một số $k$. Một mảng hai chiều S được tạo theo quy tắc này:$$ S[i][j]=A[i]*A[j]$$
- Hỏi xem là có bao nhiêu hình chữ nhật con của mảng S có tổng là $k$?
- Giới hạn:
- $1 \le N \le 8000$
- $1 \le A_i \le 100$
- $1 \le k \le 10^6$
- **Lời giải:**
- Xét tổng $T$ là tổng các ô của mảng con của $S$ có góc trên bên trái là $(i,j)$ và góc dưới bên phải là $(x,y)$ là:
$$ T=S[i][j] + S[i][j+1] + ... + S[i][y]\\ + S[i+1][j] + S[i+1][j+1] + ... + S[i+1][y]\\ + ...\\+ S[x][j]+S[x][j+1]+...+S[x][y] $$
$$T=A[i]*A[j]+A[i]*[j+1]+...+A[i]*A[y]\\ +A[i+1]*A[j]+A[i+1]*[j+1]+...+A[i+1]*A[y] \\ +...\\ + A[x]*A[j]+A[x]*[j+1]+...+A[x]*A[y] $$
$$T=A[i]*(A[j]+A[j+1]+...+A[y])\\+ A[i+1]*(A[j]+A[j+1]+...+A[y])\\ +...\\+ A[x]*(A[j]+A[j+1]+...+A[y]) $$
$$T=(A[i]+A[i+1]+...+A[x])*(A[j]+A[j+1]+...+A[y]) $$
- Ta muốn $T$ bằng với $k$ mà $T$ là tích của tổng hai đoạn con liên tiếp nên ta có thể tính trước và thống kê tất cả tổng của các đoạn con liên tiếp sau đó xét lại tất cả các ước của $k$ và dùng một ít toán để có thể lấy được đáp án.
- Độ phức tạp: $O(N^2+k)$

:::spoiler **Code mẫu:**

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll status[1000005];

const int N = 8e3 + 1;
int a[N];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    freopen("SUMK.INP", "r", stdin);
    freopen("SUMK.OUT", "w", stdout);

    int n; cin >> n;
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    int k; cin >> k;
    
    for(int i = 0; i < n; ++i) {
        int cur = 0;
        for (int j = i; j >= 0; --j) {
            cur += a[j];
            status[cur]++;
        }
    }   
    
    ll ans = 0;
    for(int i = 1; i <= k; ++i) 
        if (status[i] != 0 && k % i == 0) 
            ans += status[i] * status[k / i];
  
    cout << ans;
}

:::