Editorial for Bedao Regular Contest 02 - LEAVES
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Ý 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(); }
Comments