B. 3^A

题意

给你一个整数，让你把它分解成若干个3的幂之和（幂次小于等于10），个数小于等于20，问分解方案。（保证有解）

大概思路

直接正常模拟即可

参考代码

void solve() {
    int m;
    std::cin >> m;

    std::vector<int> a;
    while (m) {
        int now = 1;
        int cnt = 0;
        while (now <= m && cnt <= 11) {
            now *= 3;
            cnt++;
        }
        now /= 3;
        cnt--;

        m -= now;
        a.push_back(cnt);
    }
    std::cout << a.size() << "\n";
    for (auto &i : a) {
        std::cout << i << " ";
    }
}

C. Count ABC Again

题意

给你一个长度为n的字符串，以及q次查询，每次查询单点修改字符串某个位置的字符，并回答修改后的新字符串中有多少个“ABC”子串。（修改影响后续操作）

大概思路

先预处理出原来字符串中有多少个ABC子串，然后每次记录以修改位置为中心，半径为3范围内的ABC子串，单点修改前的数量以及修改后的数量，然后更新回去就行。

参考代码

void solve() {
    int n, q;
    std::cin >> n >> q;

    std::string s;
    std::cin >> s;
    s = " " + s;
    int cnt = 0;
    for (int i = 1; i <= n - 2; i++) {
        if (s.substr(i, 3) == "ABC") cnt++;
    }
    while (q--) {
        int x;
        std::string c;
        std::cin >> x >> c;

        int bf = 0, af = 0;
        for (int i = std::max(1, x - 2); i <= std::min(n - 2, x); i++) {
            if (s.substr(i, 3) == "ABC") {
                bf++;
            }
        }
        s[x] = c[0];
        for (int i = std::max(1, x - 2); i <= std::min(n - 2, x); i++) {
            if (s.substr(i, 3) == "ABC") af++;
        }
        cnt -= bf - af;
        std::cout << cnt << "\n";
    }
}

D. Buildings

题意

给你n个数，让你求出，对于每个数 $a_i$ 来说，其后面有多少个数 $a_j$ 满足：“$a_i$ 到 $a_j$ 之间没有任何一个数比 $a_j$ 大”。

大概思路

倒着跑单调栈即可，每次把栈顶小于当前元素的数弹出。

参考代码

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n), ans(n);
    for (auto &i : a) std::cin >> i;

    std::stack<int> stk;
    for (int i = n - 1; i >= 0; i--) {
        ans[i] = stk.size();
        while (stk.size() && stk.top() < a[i]) stk.pop();
        stk.push(a[i]);
    }
    for (auto &i : ans) std::cout << i << " ";
}

E. K-th Largest Connected Components

题意

给你n个节点，初始没有任何连边。现在给你q个操作如下：

• 类型 1: $1~u~v$ 将 $u$ 和 $v$ 连边.
• 类型 2: $2~v~k$ 询问与 $v$ 同处于同一个联通块内的第 $k$ 大的元素；如果不存在，输出 $-1$.

$1 \le k \le 10$

大概思路

直接用带权并查集，维护每个联通块前10大的元素即可。

参考代码

const int N=200005;
int F[N];
std::vector<int> rk[N];
int find(int x){//查询，自带路径压缩
    if (x != F[x]) {
        int fx=F[x];//暂存其亲戚
        
        for (auto &i : rk[x]) {
            rk[fx].push_back(i);
        }
        std::sort(rk[fx].rbegin(), rk[fx].rend());
        rk[fx].erase(std::unique(rk[fx].begin(), rk[fx].end()), rk[fx].end());

        if (rk[fx].size() > 10) {
            rk[fx].erase(rk[fx].begin() + 10, rk[fx].end());
        }

        F[x]=find(F[x]);
    }
    return F[x];
}
void join(int x,int y){//合并集合
    int fx = find(x), fy = find(y);
    F[fx]=fy;

    for (auto &i : rk[fx]) {
        rk[fy].push_back(i);
    }
    std::sort(rk[fy].rbegin(), rk[fy].rend());
    rk[fy].erase(std::unique(rk[fy].begin(), rk[fy].end()), rk[fy].end());

    if (rk[fy].size() > 10) {
        rk[fy].erase(rk[fy].begin() + 10, rk[fy].end());
    }
}

void solve() {
    int n, q;
    std::cin >> n >> q;
    for (int i = 1; i <= n; i++) {
        F[i] = i;
        rk[i].push_back(i);
    }

    while (q--) {
        int op, x, y;
        std::cin >> op >> x >> y;

        if (op == 1) {
            join(x, y);
        } else {
            int fv = find(x);
            if ((int)rk[fv].size() < y) {
                std::cout << -1 << "\n";
            } else {
                std::cout << rk[fv][y - 1] << "\n";
            }
        }
    }
}