Hướng dẫn giải của Thi thử Duyên hải 2021 - Lần 1 - Bài 1 - PARALLEL
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.
Tác giả:
~\color{orange}{\text{Hướng dẫn}}~
- Để 12 cạnh tạo thành hình hộp chữ nhật thì tồn tại một cách chia thành 3 nhóm sao cho thỏa cả 3 điều kiện:
Nhóm 1 gồm 4 cạnh bằng nhau để làm chiều ngang
Nhóm 2 gồm 4 cạnh bằng nhau để làm chiều cao
Nhóm 3 gồm 4 cạnh bằng nhau để làm chiều sâu
~\color{goldenrod}{\text{Tiếp cận}}~
- Sắp xếp mảng 12 phần tử lại, không mất tính tổng quát, giả sử
Nhóm 1 gồm ~a_0 \leq a_1 \leq a_2 \leq a_3~. Khi ~a_0 = a_1~ thì ~a_0 = a_1 = a_2 = a_3 \Rightarrow~ nhóm 1 thỏa
Nhóm 2 gồm ~a_4 \leq a_5 \leq a_6 \leq a_7~. Khi ~a_4 = a_7~ thì ~a_4 = a_5 = a_6 = a_7 \Rightarrow~ nhóm 2 thỏa
Nhóm 3 gồm ~a_8 \leq a_9 \leq a_{10} \leq a_{11}~. Khi ~a_8 = a_{11}~ thì ~a_8 = a_9 = a_{10} = a_{11} \Rightarrow~ nhóm 3 thỏa
~\color{purple}{\text{Độ phức tạp}}~
Có ~Q~ truy vấn. Mỗi truy vấn sort 12 phần tử và kiểm tra mất ~O(12\ log\ 12) = O(1)~
Vậy độ phức tạp là ~O(Q)~
~\color{green}{\text{Code tham khảo }}~: Sắp xếp
~^{^{\color{purple}{\text{Độ phức tạp : }} O(Q)\ \color{purple}{\text{thời gian}}\ ||\ O(Q)\ \color{purple}{\text{bộ nhớ}}}}~
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main()
{
while (true)
{
vector<int> a(12);
for (int &x : a) cin >> x;
sort(a.begin(), a.end());
if (a.back() == 0) break;
cout << (((a[0] == a[3]) && (a[4] == a[7]) && (a[8] == a[11])) ? "yes" : "no") << '\n';
}
return 0;
}
Bình luận