前言

好久不见，最近区域赛什么的有点忙，鸽了两周，不会G待补，看不懂我的文字题解的去牛客b站的官网看苯环哥哥的视频题解，讲得很好！

题解

A.小苯吃糖果

比较一下最大的数和其他两个数的和哪个大就好了

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    std::vector<int> a(3);
    int sum = 0;
    for (int i = 0; i < 3; i++) {
        std::cin >> a[i];
        sum += a[i];
    }   

    std::sort(a.begin(), a.end());
    std::cout << std::max(a[0] + a[1], a[2]);
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);
    
    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

B.小苯的排列构造

从大到小输出n到1即可， + 1 + n，比如长度为5时，a数组为，

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    int n;
    std::cin >> n;
    for (int i = n; i >= 1; i--) {
        std::cout << i << ' ';
    }
    std::cout << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);
    
    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

C.小苯的最小整数

我们发现字符串很短，最多就长度为10，暴力模拟即可。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    std::string s, ans;
    std::cin >> s;
    ans = s;
    for (int i = 0; i < s.size(); i++) {
        std::string t;
        t = s.substr(i, s.size() - i) + s.substr(0, i);
        if (t < ans) {
            ans = t;
        }
    }
    std::cout << ans << '\n';
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);
    
    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}

D E.小苯的蓄水池

带权并查集，维护联通块大小和联通块中所有数的和，每次查询就直接求平均值即可，合并的时候，用区间右端点的祖宗一直往区间左端点的祖宗上合并即可，每次把当前的“右端点”更新为上一次右端点的祖宗。

#include<bits/stdc++.h>

using i64 = long long;

struct DSU {
    std::vector<i64> f, siz, sum;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
        sum.resize(n);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        if (x > y) {
            std::swap(x, y);
        }
        siz[x] += siz[y];
        sum[x] += sum[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }

    DSU tr(n + 1);
    for (int i = 1; i <= n; i++) {
        tr.sum[i] = a[i];
    }

    while(m--) {
        int op;
        std::cin >> op;
        if (op == 1) {
            int l, r;
            std::cin >> l >> r;
            int fl = tr.find(l);
            int fr = tr.find(r);
            while(fr != fl) {
                tr.merge(fl, fr);
                r = fr - 1;
                fr = tr.find(r);
            }
        }
        else {
            int x;
            std::cin >> x;
            x = tr.find(x);
            std::cout << std::fixed << std::setprecision(6) << tr.sum[x] * 1.0 / tr.siz[x] << '\n';
        }
    }
    // std::cout << 1;
}  

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);
    
    i64 t = 1; 
    // std::cin >> t;
    while (t--) {
        solve();
    }
}

F. 小苯的字符提前

这个题建议直接去看苯环哥哥的视频题解吧，讲的很清楚，自己也可以手玩一点找找规律，思路大概就是先找到你要找到这个第k小的字符串的开头字母是哪个，比如是a，然后就去找对于每一个a的下一个跟他不同的字母是比他大还是比他小。

#include<bits/stdc++.h>

using i64 = long long;

void solve() {
    int n, k;
    std::cin >> n >> k;
    std::string s;
    std::cin >> s;
    s = ' ' + s;

    std::vector<int> cnt(26, 0);
    for (int i = 1; i <= n; i++) {
        cnt[s[i] - 'a']++;
    }   

    int sum = 0, pos = -1;
    for (int i = 0; i < 26; i++) {
        if (sum + cnt[i] >= k) {
            pos = i;
            break;
        }
        else {
            sum += cnt[i];
        }
    }

    std::vector<int> nxt(n + 1);
    for (int i = n; i >= 1; i--) {
        if (i < n && s[i] == s[i + 1]) {
            nxt[i] = nxt[i + 1];
        }
        else {
            nxt[i] = i + 1;
        }
    }

    std::deque<int> q;
    for (int i = n; i >= 1; i--) {
        if ((s[i] - 'a') != pos) continue;
        int x = nxt[i];
        if (x <= n && s[i] < s[x]) {
            q.emplace_back(i);
        }
        else {
            q.emplace_front(i);
        }
    }

    for (int i = 1; i < k - sum; i++) {
        q.pop_front();
    }
    std::cout << s[q.front()] << s.substr(1, q.front() - 1) << s.substr(q.front() + 1) << '\n';
}

signed main() {
    std::ios::sync_with_stdio(0);
    std::cout.tie(0);   
    std::cin.tie(0);
    
    i64 t = 1; 
    std::cin >> t;
    while (t--) {
        solve();
    }
}