Hướng dẫn giải của [200 đề thầy Đức] Bài 145: Đếm hình vuông
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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
Mỗi hình vuông cần 4 đoạn thẳng cùng độ dài ~L~, diện tích là ~L^2~. Cần tìm diện tích lớn nhất có thể tạo được, và số hình vuông đạt diện tích đó. Nếu không đủ 4 đoạn cùng độ dài nào thì in -1.
Diện tích tăng theo ~L~ nên chỉ cần xét độ dài ~L~ lớn nhất có ít nhất 4 đoạn. Số hình vuông cạnh ~L~ là ~cnt[L] / 4~.
Sub 1: Vét cạn đếm số đoạn bằng nhau — ~O(T \cdot N^2)~
Với mỗi đoạn ~a[i]~, duyệt cả dãy để đếm số đoạn cùng độ dài, lấy ~\lfloor same / 4 \rfloor~ hình vuông, cập nhật diện tích lớn nhất. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (int &x : a) cin >> x;
// Vét cạn: với mỗi đoạn thẳng, đếm số đoạn bằng nó bằng cách duyệt cả dãy
long long bestArea = -1;
long long bestCnt = 0;
for (int i = 0; i < n; i++) {
int same = 0;
for (int j = 0; j < n; j++) if (a[j] == a[i]) same++;
long long squares = same / 4; // mỗi hình vuông cần 4 đoạn bằng nhau
if (squares == 0) continue;
long long area = 1LL * a[i] * a[i];
if (area > bestArea) {
bestArea = area;
bestCnt = squares;
}
}
if (bestArea == -1) cout << -1 << "\n";
else cout << bestArea << " " << bestCnt << "\n";
}
return 0;
}
Sub 2: Đếm bằng mảng tần suất — ~O(T \cdot (N + 1000))~
Đếm số đoạn mỗi độ dài trong mảng ~cnt~ (độ dài không quá ~10^3~). Tìm ~L~ lớn nhất có ~cnt[L] \ge 4~, in ~L^2~ và ~cnt[L] / 4~. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
// Đếm số đoạn có mỗi độ dài (độ dài <= 1000)
vector<int> cnt(1001, 0);
for (int i = 0; i < n; i++) {
int x;
cin >> x;
cnt[x]++;
}
// Hình vuông cạnh L cần 4 đoạn dài L. Diện tích lớn nhất ứng với L lớn nhất có cnt >= 4.
int best = -1;
for (int L = 1; L <= 1000; L++) {
if (cnt[L] >= 4) best = L;
}
if (best == -1) {
cout << -1 << "\n";
} else {
long long area = 1LL * best * best;
// Số hình vuông có diện tích lớn nhất chính là cnt[best] / 4
cout << area << " " << cnt[best] / 4 << "\n";
}
}
return 0;
}
Bình luận