Editorial for Thi thử Duyên hải 2021 - Lần 1 - Bài 1 - PARALLEL


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: SPyofgame

~\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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.