Hướng dẫn giải của Chọn quà (đề TP.HCM 2021)
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 đặt vợt để nhận được nhiều quà nhất. Quà nhận được là quà nằm hoàn toàn bên trong 4 cạnh vợt (quà trên cạnh không tính). Vợt có ~K~ mối nối trên mỗi cạnh nên phần bên trong là một hình vuông gồm ~(K-2) \times (K-2)~ mối nối. Bài toán trở thành: tìm hình vuông ~(K-2) \times (K-2)~ ô trong bảng ~D \times R~ chứa nhiều dấu * nhất.
Lưu ý: khung vợt phải nằm hoàn toàn trên các đường của lưới, nên phần bên trong ~(K-2) \times (K-2)~ mối nối phải cách mép bảng ít nhất 1 mối nối: góc trên-trái của phần bên trong chạy từ hàng 1 đến ~D-L-1~ và cột 1 đến ~R-L-1~ (đánh số từ 0, ~L = K-2~).
Sub 1: Vét cạn — ~O(D \cdot R \cdot K^2)~, dùng khi ~D, R \le 100~
Thử mọi vị trí góc trên-trái của hình vuông ~(K-2) \times (K-2)~, đếm trực tiếp số dấu * bên trong bằng hai vòng lặp lồng nhau.
Nếu chỉ nộp sub này: đúng 18/20 test (đúng hết 10 test thuộc miền của nó, 2 test lớn quá giờ).
Sub 2: Tổng cộng dồn 2 chiều — ~O(D \cdot R)~
Gọi ~P[i][j]~ là số quà trong phần bảng gồm các hàng ~< i~ và cột ~< j~. Số quà trong một hình vuông được tính trong ~O(1)~ bằng ~P[b][d] - P[a][d] - P[b][c] + P[a][c]~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~D, R, K~ và bảng từ file chonqua.inp (có freopen vì máy chấm dùng file), nếu ~D, R \le 100~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int D, R, K;
int L; // canh vung ben trong vot: (K-2) x (K-2) moi noi
vector<string> g; // g[i][j] = '*' neu tai moi noi (hang i, cot j) co qua
// Sub 1: vet can. Thu moi vi tri goc tren-trai (r, c) cua vung ben trong L x L, dem qua truc tiep.
// Do phuc tap ~O(D*R*K^2), dung khi D, R <= 100.
void sub1() {
int best = 0;
// Khung vot nam tron trong luoi nen vung ben trong cach mep it nhat 1 moi noi
for (int r = 1; r + L <= D - 1; r++)
for (int c = 1; c + L <= R - 1; c++) {
int cnt = 0;
for (int i = r; i < r + L; i++)
for (int j = c; j < c + L; j++)
if (g[i][j] == '*') cnt++;
best = max(best, cnt);
}
cout << best << "\n";
}
// Sub 2: mang tong cong don P[i][j] = so qua trong cac moi co hang < i va cot < j.
// Dem so qua trong mot hinh vuong L x L trong O(1). Tong cong O(D*R).
void sub2() {
vector<vector<int>> P(D + 1, vector<int>(R + 1, 0));
for (int i = 0; i < D; i++)
for (int j = 0; j < R; j++)
P[i + 1][j + 1] = P[i][j + 1] + P[i + 1][j] - P[i][j] + (g[i][j] == '*');
int best = 0;
// Khung vot nam tron trong luoi nen vung ben trong cach mep it nhat 1 moi noi
for (int r = 1; r + L <= D - 1; r++)
for (int c = 1; c + L <= R - 1; c++) {
int cnt = P[r + L][c + L] - P[r][c + L] - P[r + L][c] + P[r][c];
best = max(best, cnt);
}
cout << best << "\n";
}
int main() {
freopen("chonqua.inp", "r", stdin);
freopen("chonqua.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> D >> R >> K;
L = K - 2;
g.resize(D);
for (int i = 0; i < D; i++) cin >> g[i];
if (D <= 100 && R <= 100) sub1();
else sub2();
return 0;
}
Bình luận