Hướng dẫn giải của [2425 KS1] Bài 4: Xóa số
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cần chọn x phần tử xóa ở đầu và y phần tử xóa ở cuối (cả hai dãy đều xóa như vậy) để giá trị ghép cặp còn lại lớn nhất. Giá trị là tổng A[x+i] \cdot B[n-1-y-i] với i chạy trên các vị trí còn lại.
Đặt r = n-1-y và s = x + r. Khi đó A[i] ghép với B[s-i], và đoạn cần cộng là i từ x đến s-x. Nhờ vậy, với mỗi s dựng một mảng tiền tố của các tích A[i] \cdot B[s-i], và mọi cặp (x, r) tính được trong O(1).
Sub 1: Vét cạn mọi cặp (x, y) — ~O(n^3)~, dùng khi ~n \le 100~
Thử mọi x, y với x + y < n và tính trực tiếp giá trị. Nếu chỉ nộp sub này: đúng 10/10 test.
Sub 2: Tiền tố theo tổng chỉ số — ~O(n^2)~
Duyệt mọi s, với mỗi s dựng mảng tiền tố rồi lấy tổng đoạn cho từng x. Tổng số phép tính là O(n^2) với n \le 2000.
Bẫy: giá trị có thể âm, tổng có độ lớn khoảng 2 \cdot 10^9 nên dùng long long.
Nếu chỉ nộp sub này: đúng 10/10 test.
Chương trình hoàn chỉnh
Hàm main đọc hai dãy. Nếu n \le 100 gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A, B; // hai day, chi so 0..n-1
// Sub 1: vet can. Thu moi cap (x, y) voi x + y < n, tinh gia tri cua day con A[x..n-1-y] va B[x..n-1-y]
// (ghep A[x+i] voi B[n-1-y-i]). O(n^3). Dung khi n <= 100
void sub1() {
long long best = LLONG_MIN;
int bx = 0, by = 0;
for (int x = 0; x < n; x++)
for (int y = 0; x + y < n; y++) {
int L = n - x - y;
long long val = 0;
for (int i = 0; i < L; i++) val += A[x + i] * B[n - 1 - y - i];
if (val > best) { best = val; bx = x; by = y; }
}
cout << bx << " " << by << "\n" << best << "\n";
}
// Sub 2: dat r = n-1-y, dat s = x + r. Gia tri = sum_{i=x}^{s-x} A[i] * B[s-i] (vi B[x+r-i] = B[s-i]).
// Voi moi s co the tinh mang tong tien to cua t_i = A[i]*B[s-i], roi moi x co the lay tong doan trong O(1).
// Tong O(n^2).
void sub2() {
long long best = LLONG_MIN;
int bx = 0, by = 0;
for (int s = 0; s <= 2 * n - 2; s++) {
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) {
long long t = 0;
if (s - i >= 0 && s - i < n) t = A[i] * B[s - i];
pre[i + 1] = pre[i] + t;
}
int xlo = max(0, s - n + 1);
for (int x = xlo; x <= s - x; x++) { // r = s - x phai >= x va <= n-1
int r = s - x;
long long val = pre[r + 1] - pre[x];
if (val > best) { best = val; bx = x; by = n - 1 - r; }
}
}
cout << bx << " " << by << "\n" << best << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
A.assign(n, 0);
B.assign(n, 0);
for (int i = 0; i < n; i++) cin >> A[i];
for (int i = 0; i < n; i++) cin >> B[i];
if (n <= 100) sub1();
else sub2();
return 0;
}
Bình luận