Hướng dẫn giải của Bedao Regular Contest 02 - LEAVES


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.

Tác giả: bedao

Ý tưởng 1

Gọi ~cnt_i~ là đếm số node và lá có độ cao là i

Dễ thấy với từng ~i~ độ cao muốn nó thành một cây nhị phân đầy đủ thì số lượng node và lá có độ cao là ~i~ đều phải là một số chẵn, để đếm số lượng node và lá có độ cao là ~i~ thì ta có các nhận xét như sau:

  • Tổng số lượng node có độ cao ~i~ bằng tổng số node và lá có độ cao là ~i+1~ chia cho ~2~ hay ~\frac{cnt_{i+1}}{2}~

Vậy ta chỉ cần duyệt ngược lại từ độ cao cao nhất về độ cao là ~1~, mỗi lần duyệt ta kiểm tra xem với độ cao ~i~ có số lượng node và lá là ~cnt_i~ thì nó có thỏa mãn là cây nhị phân không khi và chỉ khi ~cnt_i~ là một số chẵn và nếu thỏa mãn thì ta cập nhật số lượng node và lá cho độ cao ~i-1~

Lưu ý: Ta cần phải xét xem số lượng gốc của cây hay là ~cnt_0~ có thỏa mãn luôn luôn bằng ~1~, nếu thỏa mãn cùng với điều kiện trên thì đây là cây nhị phân đầy đủ.


Ý tưởng 2

Sử dụng hàng đợi ưu tiên - priority queue để mô phỏng lại cách từ lá lên đỉnh gốc

Gọi ~pq~ là tập hợp độ cao của nút lá và phần tử đầu tiên của ~pq~ chính là nút lá có độ sâu cao nhất

Khi ~pq~ vẫn còn nhiều hơn ~1~ phần tử thì ta sẽ lấy trong ~pq~ hai phần tử mỗi lượt là:

  • ~best~ là nút lá có độ cao cao nhất

  • ~secondBest~ là nút lá có độ cao cao nhì ( tức có độ cao bé hơn hoặc bằng ~best~ )

Nếu ~best = secondBest~ thì ta sẽ thêm vào ~pq~ độ cao ~best-1~ ( hoặc ~secondBest-1~ ) và có khả năng tạo được cây nhị phân đày đủ, ngược lại không thể tạo được cây nhị phân đầy đủ

Vậy chạy đến khi ~pq~ chỉ còn ~1~ phần tử thì kiểm tra xem phần tử còn lại duy nhất trong ~pq~ đó có độ cao bằng ~0~ hay không, nếu không thì không thể tạo được cây nhị phân đầy đủ, ngược lại thì tạo được.

Code mẫu

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
#define ios ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define nd second
#define st first
using namespace std;
const int N = 1e5 + 5;
int n, a[N];
void program(){
    cin >> n;
    map<int,int,greater<int> > m;
    for (int i = 1; i <= n; i++) cin >> a[i], m[a[i]]++;

    for (auto i : m){
        if (i.nd % 2 == 1 && i.st != 0){
            cout << "NO\n";
            return;
        }
        if (i.st == 0 && i.nd != 1){
            cout << "NO\n";
            return;
        } 
        if (i.st == 0 && i.nd == 1){
            break;
        }
        m[i.st - 1] += (i.nd / 2);
    }
    cout << "YES\n";
}
signed main(){
    ios;
    int test;
    cin >> test;
    while(test--) program();
}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.