Hướng dẫn giải của [Beginner Free Contest 02] MAKERECT
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
Chọn 4 que tạo hình chữ nhật khi và chỉ khi có thể ghép chúng thành hai cặp que bằng nhau. Diện tích lớn nhất là tích hai cặp có độ dài lớn nhất.
Sub 1: Vét cạn 4 que — ~O(n^4)~, dùng khi ~n \le 50~
Thử mọi bộ 4 que khác nhau, sắp xếp 4 độ dài ~v_0 \le v_1 \le v_2 \le v_3~; nếu ~v_0 = v_1~ và ~v_2 = v_3~ thì diện tích là ~v_0 \cdot v_2~. Nếu chỉ nộp sub này: đúng 6/20 test.
Sub 2: Vét cạn trên các cặp — ~O(m^2)~, dùng khi ~n \le 2000~
Gom mỗi độ dài thành ~\lfloor cnt/2 \rfloor~ cặp (~m~ là số cặp). Thử mọi cặp hai cặp trong danh sách, lấy tích lớn nhất. Nếu chỉ nộp sub này: đúng 14/20 test.
Sub 3: Sắp xếp — ~O(n \log n)~
Cùng cách gom cặp, sắp các cặp giảm dần. Tích lớn nhất của hai số dương chính là tích hai số lớn nhất. Nếu có ít hơn 2 cặp thì đáp án là 0. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc ~n~ và các độ dài, nếu ~n \le 50~ gọi sub1, nếu ~n \le 2000~ gọi sub2, ngược lại gọi sub3.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> A; // A[0..n-1]
// Hinh chu nhat can 4 que: sau khi sap xep v0 <= v1 <= v2 <= v3, phai co v0 = v1 va v2 = v3.
// Dien tich = v0 * v2.
// Sub 1: vet can O(n^4) (n <= 50): thu moi bo 4 que khac nhau.
void sub1() {
long long best = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
for (int k = j + 1; k < n; k++)
for (int l = k + 1; l < n; l++) {
vector<long long> v = {A[i], A[j], A[k], A[l]};
sort(v.begin(), v.end());
if (v[0] == v[1] && v[2] == v[3]) best = max(best, v[0] * v[2]);
}
cout << best << "\n";
}
// Danh sach P: moi cap que bang nhau cho mot phan tu (gia tri xuat hien cnt lan cho cnt/2 cap)
vector<long long> buildPairs() {
map<long long, int> cnt;
for (long long x : A) cnt[x]++;
vector<long long> P;
for (auto &it : cnt)
for (int t = 0; t < it.second / 2; t++) P.push_back(it.first);
return P;
}
// Sub 2: O(m^2) voi m = so cap (n <= 2000): thu moi cap hai cap
void sub2() {
vector<long long> P = buildPairs();
long long best = 0;
for (size_t i = 0; i < P.size(); i++)
for (size_t j = i + 1; j < P.size(); j++)
best = max(best, P[i] * P[j]);
cout << best << "\n";
}
// Sub 3: O(n log n): hai canh lon nhat trong cac cap la tich can tim
void sub3() {
vector<long long> P = buildPairs();
if (P.size() < 2) { cout << 0 << "\n"; return; }
sort(P.rbegin(), P.rend());
cout << P[0] * P[1] << "\n";
}
int main() {
cin >> n;
A.resize(n);
for (auto &x : A) cin >> x;
if (n <= 50) sub1();
else if (n <= 2000) sub2();
else sub3();
return 0;
}
Bình luận