# Đề TS10 - BRVT - 2024: Editorial

>[!Note] 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 2024 - 2025.
>
>**Bạn đọc có thể nộp và chấm bài (test tự sinh)** [TẠI ĐÂY](https://chuyentin-brvt.online/contest/algi_ts10_15_24).
>
>:::info
>Chuẩn bị bởi ==team Logica==, thuộc khuôn khổ dự án [**The Algitect (ALGI Project)**](https://www.facebook.com/algitect.project)
>:::

[toc]

## Bài 1

### Tóm tắt đề bài

Cho số nguyên dương $N$.

**Yêu cầu:** Hãy đếm số lượng các ước số dương của $N$.

**Dữ liệu đảm bảo:** $10 \le N \le 10^{12}$.

**Ràng buộc:**
- $50\%$ số điểm tương ứng với $1 \le N \le 10^6$
- $50\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Duyệt $i$ từ $1$ đến $n$ và đếm các số $i$ mà ==$n$ chia hết cho $i$==.
> Tức là $n \bmod i = 0$.

**Độ phức tạp thời gian:** $O\left( n \right)$.

:::success
:::spoiler Code

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

long long n, kq;

int main() {
    cin >> n;

    for (long long i = 1; i <= n ;++i) {
        if (n % i == 0) {
            kq++;
        }
    }
    
    cout << kq;
    
    return 0;
}

:::

### Subtask 2

>[!Tip] Nhận xét
> Giả sử $n$ có một ước là $x$, $y = \frac n x$ cũng là một ước của $n$.
> :::success
> Quan sát thấy, luôn luôn có ít nhất một trong hai số nhỏ hơn hoặc bằng $\sqrt n$
> :::

Do đó, ta duyệt $i$ từ $1$ đến $\left \lfloor \sqrt n \right \rfloor$, nếu tìm thấy số $i$ mà $n \bmod i = 0$, ngoài đếm ước $i$, ta đếm thêm cả ước $\frac n i$ của $n$.

:::danger
**Lưu ý:** Trong trường hợp $i \times i = n$, số $i$ có thể bị đếm $2$ lần.
:::

**Độ phức tạp thời gian:** $O\left( \sqrt n \right)$.

:::success
:::spoiler Code

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

long long n, kq;

int main() {
    cin >> n;

    //i <= sqrt(n) tương đương i*i <= n
    for (long long i = 1; i*i <= n; ++i) {
        if (n % i == 0) {
            kq += 2;
            if (i*i == n) {
                kq--;
            }
        }
    }

    cout << kq;
    
    return 0;
}

:::

## Bài 2

### Tóm tắt đề bài

Cho một số nguyên dương $N$ có số lượng chữ số không vượt quá $10^5$.

**Yêu cầu:** Hoán vị các chữ số của $N$, sao cho sau khi hoán vị ta thu được một số nguyên dương lớn nhất là bội của số $30$.

**Ràng buộc:**
- $50\%$ số điểm tương ứng với số lượng chữ số của $N$ không vượt quá $10$
- $50\%$ số điểm không có ràng buộc gì thêm.

### Về bội số của 30

Một số chia hết cho $30$ khi và chỉ khỉ số đó thỏa mãn:
- Số đó chia hết cho $3$, nghĩa là ==tổng các chữ số chia hết cho $3$==.
- Số đó chia hết cho $10$, nghĩa là ==có số $0$ ở cuối==.

### Subtask 1

Ta thử ==tất cả các cách hoán vị các chữ số của $N$== và tìm số lớn nhất thỏa mãn tất cả điều kiện ở trên.

Để dễ thao tác, ta sử dụng hàm `next_permutation()` có sẵn trong thư viện STL của C++.

**Độ phức tạp thời gian:** $O \left( n! \right)$

### Subtask 2

Ta sắp xếp lại các chữ số theo thứ tự giảm dần để số đạt giá trị lớn nhất.

Trùng hợp, khi đó số $0$ (nếu có) của $N$ cũng sẽ được dồn về cuối số, giúp ta thỏa mãn điều kiện thứ $2$.

Khi ta sắp xếp lại như vậy, tổng các chữ số không bị thay đổi, nên ta kiểm tra xem tổng này có chia hết cho $3$ hay không.

>[!Tip]
> Để dễ thao tác, ta nên sử dụng kiểu dữ liệu `string` để lưu số $N$.

**Độ phức tạp thời gian:** $O \left( n \log n \right)$ với $n$ là số lượng chữ số của $N$.

:::success
:::spoiler Code

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

int sumDig(string s) {
	int ret = 0;
	for (char x : s) {
		ret += (x - '0');
    }

	return ret;
}

int main() {
	string s;
	cin >> s;
	sort(all(s), greater<char>());

	if (s.back() != '0' || sumDig(s) % 3) cout << -1;
	else cout << s;

	return 0;
}

:::

## Bài 3

### Tóm tắt đề bài

Cho dãy $A$ gồm $N$ số nguyên dương. Bằng cách ghi dãy $A$ lặp lại vô hạn lần ta thu được dãy $B$.

**Yêu cầu:** Cho số nguyên dương $K, P$. Tính tổng $K$ phần tử liên tiếp trong dãy $B$ bắt đầu từ phần tử có chỉ số $P$.

**Dữ liệu đảm bảo:**
- $1 \le N \le 10^5$;
- $1 \le K, P \le 10^9$;
- $1 \le A_i \le 10^3$.

**Ràng buộc:**
- $50\%$ số điểm tương ứng với $1 \le K \le 10^4, 1 \le P \le 10^5$
- $50\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Thực hiện mô phỏng theo đề bài, ta duy trì một biến vị trí để di chuyển tăng dần, nếu vị trí lớn hơn $n$, ta cập nhật lại biến về $1$.

>[!Tip] Mẹo
> Sử dụng phép toán $\bmod$ để cập nhật lại vị trí.

**Độ phức tạp thời gian:** $O \left( P \right)$.

:::success
:::spoiler Code

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

long long n, kq, l, r, a[1000009], k ,p;

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

:::

### Subtask 2

>[!Tip] Nhận xét
> Dãy $B$ là dãy $A$ lặp đi lặp lại vô tận.
>
> Do đó, tổng của $K$ phần tử liên tiếp mà đề bài yêu cầu ta tính cũng được tạo thành từ nhiều tổng của cả dãy $A$ cộng lại và một ít số bị lẻ ra.
>
> :::success
> Ta chỉ cần duyệt để tính các số bị lẻ ra, còn nhóm tổng của $A$ có thể tính nhanh.
> :::

**Độ phức tạp thời gian:** $O(n)$.

:::success
:::spoiler Code

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

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

int main() {
	cin >> n >> k >> p;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		sum += A[i];
	}
    
    A[0] = A[n];

	p %= n;
	if (!p) p = n;
    
    //Số lượng nhóm có tổng = A
	long long cycle = k / n;
    
    //Phần bị lẻ ra
	long long rem = k % n;

	long long res = cycle * sum;
	for (int i = p; i <= p + rem - 1; i++) {
		res += A[i % n];
	}

	cout << res;

	return 0;
}

:::

## Bài 4

### Tóm tắt đề bài

Cho dãy $B$ gồm các số nguyên $B_1, B_2, B_3, \dots, B_N$ được gọi là dãy lõm nếu tồn tại chỉ số $i$ $(1 \lt i \lt N)$ sao cho $B_1 > B_2 > \dots > B_i < B_{i+1} < \dots < B_N$.

**Yêu cầu:** Cho trước dãy $A$ gồm $N$ số nguyên dương $A_1, A_2, \dots, A_N$. Hãy tìm ==dãy con lõm có độ dài lớn nhất==.

**Dữ liệu đảm bảo:** $2 \lt N \le 10^5$ và $1 \le A_i \le 10^9$.

**Ràng buộc:**
- $20\%$ số điểm tương ứng với $2 \le N \le 20$.
- $30\%$ số điểm tương ứng với $20 \lt N \le 5000$.
- $50\%$ số điểm không có ràng buộc gì thêm.

### Subtask 1

Sinh tất cả dãy con của $A$, kiểm tra tính hợp lệ, và lấy độ dài dãy con dài nhất.

**Độ phức tạp thời gian:** $O(2^n)$.

### Subtask 2

>[!Tip] Nhận xét
>Một ==dãy con lõm== là hợp bởi một ==dãy con giảm== và một ==dãy con tăng== (mỗi dãy gồm ít nhất hai phần tử).

Áp dụng ==quy hoạch động== cơ bản.

- **Định nghĩa:**
- $F_i$ là dãy con giảm dài nhất kết thúc tại $i$.
- $G_i$ là dãy con tăng dài nhất bắt đầu tại $i$.
- **Khởi gán:** $F_i = G_i = 1 \; \forall \; i$ (dãy con một phần tử).
- **Công thức:**
- $F_i = \max(F_j + 1)$ với $j \lt i$ và $A_j \gt A_i$ (thêm $A_i$ vào một dãy kết thúc ở $A_j$).
- $G_i = \max(F_j + 1)$ với $j \gt i$ và $A_j \gt A_i$ (thêm $A_i$ vào một dãy kết thúc ở $A_j$).

Khi đó, ở mỗi vị trí $i$ từ $1$ đến $n$, nếu $F_i \ge 2$ và $G_i \ge 2$ thì có một dãy con lõm nhận $i$ làm điểm thấp nhất (điểm lõm) có độ dài là:
$$
F_i + G_i - 1
$$

**Độ phức tạp thời gian:** $O(n^2)$.

:::success
:::spoiler Code

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

long long n, a[1000009], F[1000009], G[1000009], kq;

int main() {
    cin >> n;
    
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    
    for (int i = 1; i <= n; i++) {
        F[i] = 1;
        for (j = 1; j <= i-1; j++) {
            if (a[j] > a[i]) {
                F[i] = max(F[i], F[j]+1);
            }
        }
    }
        
    for (int i = n; i >= 1; i--) {
        G[i] = 1;
        for (j = n; j >= i+1; j--) {
            if (a[j] > a[i]) {
               G[i] = max(G[i], G[j]+1);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) {
        kq = max(kq, F[i] + G[i] - 1);
    }

    cout << kq;
    
    return 0;
}

:::

### Subtask 3

Tư tưởng kế thừa từ subtask trước, tuy nhiên cần cải tính việc tính $F$ và $G$.

Bạn đọc tham khảo bài viết về giải thuật **dãy con tăng dài nhất** nâng cao [**sau đây**](https://viblo.asia/p/bai-toan-lis-nang-cao-va-mot-so-ung-dung-cua-lis-924lJgd65PM).

**Độ phức tạp thời gian:** $O(n \log n)$.

:::success
:::spoiler Code

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

const int N = 1e5;
int n, A[N+1], F[N+1], G[N+1];
vector<int> V;

int findPos(int x) {
    int l = 0, r = V.size() - 1, ret = 0;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (V[mid] <= x) {
            ret = mid;
            r = mid - 1;
        } else
            l = mid + 1;
    }

    return ret;
}

void initLtoR() {
    V.clear();
    for (int i = 1; i <= n; i++) {
        if (V.empty() || V.back() > A[i]) {
            V.pb(A[i]);
            F[i] = V.size();
        } else {
            int pos = findPos(A[i]);
            V[pos] = A[i];
            F[i] = pos + 1;
        }
    }
}

void initRtoL() {
    V.clear();
    for (int i = n; i >= 1; i--) {
        if (V.empty() || V.back() > A[i]) {
            V.pb(A[i]);
            G[i] = V.size();
        } else {
            int pos = findPos(A[i]);
            V[pos] = A[i];
            G[i] = pos + 1;
        }
    }
}

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

    initLtoR();
    initRtoL();

    int res = 0;
    for (int i = 1; i <= n; i++) {
        if (F[i] >= 2 && G[i] >= 2) {
            res = max(res, F[i] + G[i] - 1);
        }
    }

    cout << res;

    return 0;
}

:::