Đề HSG9 - BRVT - 2023: Editorial

Bài 1: Tìm ước chung lớn nhất (6 điểm)

Cho dãy số nguyên dương

$A_1,A_2,\dots ,A_n$

$(1\le n\le 2\cdot {10}^5)$

$(1\le A_i\le {10}^6)$.

Tìm ước chung lớn nhất của hai số sao cho giá trị đó là lớn nhất.

Brute - force:

Duyệt tất cả các cặp số của dãy và tính ước chung lớn nhất, lấy kết quả là giá trị lớn nhất.

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

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

Code

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

const int N = 2e5;
int n, res, A[N+1];

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		for (int j = 1; j <= i-1; j++) {
			res = max(res, __gcd(A[i], A[j]));
        }
	}

	cout << res;

	return 0;
}

Accepted:

Nhận thấy

$A_i\le {10}^6$, ta có thể thực hiện thuật toán như sau:

Với mỗi số

$i$ từ

$1\to {10}^6$, ta duyệt qua tất cả các bội của

$i$, nếu gặp một số tồn tại trong dãy

$a$, ta tăng

$cn{t}_i$ lên

$1$ đơn vị.

Sau khi chạy xong thuật toán trên, ta có

$cn{t}_i$ là số lượng số trong dãy

$A$ nhận

$i$ là ước.

Đáp án của bài toán là

$i$ lớn nhất sao cho

$cn{t}_i\ge 2$.

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

$O({10}^6\log {10}^6)$.

Lưu ý:

Thuật toán trên được gọi là "sàng ước". Nhiều người nhầm tưởng thuật toán này có độ phức tạp thời gian lớn, tuy nhiên, vì số lượng bội số không ngừng giảm khi số tăng lên, nên thực chất thuật toán này chạy rất nhanh.

Nếu coi

$n$ là giới hạn để duyệt

$i$, ta có thể tính được độ phức tạp thời gian của thuật toán này như sau:

$$\sum _{i=1}^n\frac{n}{i}\approx n\log n$$

Code

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

const int N = 1e6;
int n, cnt[N+1], ex[N+1];

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

	for (int i = 1; i <= N; i++) {
		for (int j = i; j <= N; j += i) {
			cnt[i] += ex[j];
        }
    }

	for (int i = N; i >= 1; i--) {
		if (cnt[i] >= 2) {
			cout << i;
			break;
		}
    }

	return 0;
}

Bài 2: Đố vui tin học (6 điểm)

Cho dãy số nguyên dương

$A_1,A_2,\dots ,A_n$

$(n\le {10}^4)$.

Xác định độ dài dãy con tăng dài nhất của dãy

$A$, sao cho số sau phải lớn hơn số trước ít nhất

$k$

$(k\le {10}^3)$.

Định nghĩa:

Dãy con: Một dãy số được hình thành bằng cách xóa một số phần tử (hoặc không xoá phần tử nào) trong dãy ban đầu và không làm thay đổi thứ tự của các phần tử còn lại.
VD:

$3,11,4$ là một dãy con của dãy

$3,2,11,4,5$.

$\sum _{i=a}^{b}i$ : Tổng các số từ

$a\to b$.

Brute - force:

Quay lui thử tất cả các dãy con.

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

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

Accepted:

Quy hoạch động cơ bản.

Định nghĩa

$d{p}_i$ là dãy con dài nhất thỏa mãn yêu cầu đề bài và bắt buộc kết thúc tại

$a_i$.

Khởi gán

Công thức quy hoạch động:

• $d{p}_i=1$
  $(1\le i\le n)$: Khởi gán trường hợp dãy có một phần tử.
• $d{p}_i=max(d{p}_i,d{p}_j+1)$
  $(\mathrm{\forall }j<i,a_i-a_j\ge k)$.

Kết quả:

$max(d{p}_1,d{p}_2,\dots ,d{p}_n)$.

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

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

Code

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

const int N = 1e4;
int n, k, res, A[N+1], dp[N+1];

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

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

		res = max(res, dp[i]);
	}

	cout << res;

	return 0;
}

Bài 3: Trò chơi (8 điểm)

Cho

$n$ ô vuông, mỗi ô vuông có giá trị năng lượng

$h_i$

$(1\le n\le {10}^5)$.

Nếu đang ở ô vuông thứ

$i$, chỉ có thể nhảy đến ô

$i+1,i+2,\dots ,i+k$

$(1\le k\le {10}^3)$.

Để di chuyển từ ô

$i$ đến ô

$j$ cần chi phí năng lượng là

$|h_i-h_j|$.

Tìm chi phí nhỏ nhất để đi từ ô

$1$ đến ô

$n$.

Accepted:

Quy hoạch động cơ bản.

Định nghĩa

$d{p}_i$ là chi phí nhỏ nhất để nhảy từ ô

$1$ đến ô

$i$.

Công thức quy hoạch động:

• $d{p}_1=0$: Khởi gán.
• $d{p}_i=max(d{p}_i,d{p}_j+|h_i-h_j|)$
  $(max(1,i-k)\le j<i)$

Kết quả:

$d{p}_n$.

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

$O(n\cdot k)$.

Code

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

const int N = 1e5;
int n, k, H[N+1], dp[N+1];

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

	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i-1] + abs(H[i] - H[i-1]);
		for (int j = i-2; j >= max(1, i-k); j--) {
			dp[i] = min(dp[i], dp[j] + abs(H[i] - H[j]));
        }
	}

	cout << dp[n];

	return 0;
}