Hướng dẫn giải của [200 đề thầy Đức] Bài 106: Các hình chữ nhật có cùng chu vi
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
Hình chữ nhật có chu vi N thì N phải chẵn; gọi s = N/2 là tổng hai cạnh. Với cạnh a ≤ b = s - a, diện tích là a·(s - a). Vì a chạy từ 1 đến s/2 nên các diện tích khác nhau và tăng dần theo a.
Sub 1: Vét cạn cặp cạnh — ~O(N^2)~
Thử mọi cặp a ≤ b, nếu 2(a + b) = N thì thêm diện tích a·b vào tập hợp (tự sắp xếp và loại trùng). Đúng nhưng chậm, nên bị TLE ở nhiều test. Đạt 1/21 test, TLE 20 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;
// Vet can: thu moi cap canh nguyen duong a <= b, kiem tra chu vi 2(a+b) = N
set<long long> areas;
for (int a = 1; a <= N; a++)
for (int b = a; b <= N; b++)
if (2 * (a + b) == N) areas.insert((long long)a * b);
if (areas.empty()) {
cout << -1 << "\n";
} else {
bool first = true;
for (long long s : areas) { // set tu sap xep tang dan
if (!first) cout << ' ';
cout << s;
first = false;
}
cout << "\n";
}
}
return 0;
}
Sub 2: Duyệt một cạnh — ~O(N)~
Nếu N lẻ thì in -1. Nếu N chẵn, duyệt a từ 1 đến s/2 và in a·(s - a) theo thứ tự tăng dần. Đạ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<long long> res;
// Chu vi N chan thi a + b = N/2 = s. Voi a <= b, a tu 1 den s/2,
// dien tich a*(s-a) tang dan theo a nen da duoc sap xep va khac nhau
if (N % 2 == 0) {
int s = N / 2;
for (int a = 1; a <= s - a; a++)
res.push_back((long long)a * (s - a));
}
if (res.empty()) {
cout << -1 << "\n";
} else {
for (size_t i = 0; i < res.size(); i++) {
if (i) cout << ' ';
cout << res[i];
}
cout << "\n";
}
}
return 0;
}
Bình luận