B - 3^A

3进制，总是贪心使用高位，使得使用的数目最小

void solve() {
    vector<int> b(20);
    b[0] = 1;
    for (int i = 1; i <= 10; i ++ ) b[i] = b[i - 1] * 3;
    int m;
    cin >> m;
    vector<int> ans;
    for (int j = 10; j >= 0; j -- )
        if (b[j] <= m){
            int t = m / b[j];
            m -= t * b[j];
            while (t -- ) ans.push_back(j);
        }
    cout << ans.size() << '\n';
    for (auto x : ans)
        cout << x << ' ';
}

D - Buildings

熟练使用数据结构栈Stack

#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1), ans(n + 1);
    stack<int> st;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];
    for (int i = n; i >= 1; i -- ){
        int x = a[i];
        while (!st.empty() && x > st.top()) st.pop();
        st.push(x);
        ans[i - 1] = st.size();
    }
    for (int i = 1; i <= n; i ++ ){
        cout << ans[i] << ' ';
    }
}

E - K-th Largest Connected Components

联系通路，并查集
合并并查集时需要合并2个并查集内的顶点，显然Set求有序。
如果记录全部的点，一次会最多记录 $n*(n+1)/2$ 个顶点，合并 $n$ 次显然会超时。
注意到 $MAX-K$ 为10，所以第 $k-th$ 大只与前 $MAX-K$ 有关。所以只合并时，只记录前 $MAX-K$ 大即可。
(寻找2个集合的前 $MAX_K$ 大或与会十分麻烦，不如分别将2的集合内的前 $MAX_K$ 大合并。因为大集合的前 $MAX_K$ 大只与 2的小集合各自的前 $MAX_K$ 大有关.)
时间复杂度为 $O(MKlog{2K})$

const int N = 2e5 + 10;

int n, m;
set<int> se[N];
int p[N];

int find(int x){
    return p[x] == x ? x : p[x] = find(p[x]);
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ ) p[i] = i, se[i].insert(i);
    while (m -- ){
        int op, x, y;
        cin >> op >> x >> y;
        if (op == 1){
            int px = find(x), py = find(y);
            if (px == py) continue;
            else{
                p[px] = py;
                //py祖宗
                int k = 0;
                //前10个
                while (!se[px].empty() && k <= 10){
                    k ++;
                    int mx = *(--se[px].end());
                    se[py].insert(mx);
                    se[px].erase(mx);
                }
            }
        }else{
            //输出
            int px = find(x);
            if (se[px].size() < y) cout << -1 << '\n';
            else{
                vector<int> v;
                while (y){
                    int mx = *(--se[px].end());
                    se[px].erase(mx);
                    v.push_back(mx);
                    y -- ;
                    if (!y){
                        cout << mx << '\n';
                    }
                }
                for (auto mx : v) se[px].insert(mx);
            }
        }
    }
}