20250817 LiveDream 模拟赛总结

__JCY__ · 2025-08-18 16:37:14 · 个人记录

总结

炸大分

T1

签到，每次把 A 丢到后面，如果丢不了了直接清空。

#include <bits/stdc++.h>
#define int long long

using namespace std;

const int kMaxN = 5e5 + 5;

int cnt, n, ans;
string s;

signed main() {
    cin >> s, n = s.size(), s = " " + s;
    for (int i = 1; i <= n; i++) {
        if (s[i] == 'A') cnt++;
        else if (i + 1 <= n && s[i] == 'B' && s[i + 1] == 'C') {
            ans += cnt, i++;
        } else cnt = 0;
    }
    cout << ans << '\n';
    return 0;
} 

T2

考虑到在一个连通块里如果边数大于等于点数，那么一定可以供应，并不用关心怎么供应的。考虑贪心，从大往下连，使用并查集维护边和点数。

#include <bits/stdc++.h>
#define i64 long long

using namespace std;

const i64 kMaxN = 2e5 + 5;

struct N{
    i64 u, v, w;
} a[kMaxN];

i64 Fa[kMaxN], edge[kMaxN], note[kMaxN], n, m, ans;

i64 F(i64 x) {
    return Fa[x] == x ? x : Fa[x] = F(Fa[x]);
}

bool cmp(N A, N B) {
    return A.w > B.w;
}

signed main() {
    i64 T;
    for (cin >> T; T; T--) {
        cin >> n >> m, ans = 0;
        for (i64 i = 1; i <= n; i++) {
            Fa[i] = i, edge[i] = 0, note[i] = 1;
        }
        for (i64 i = 1; i <= m; i++) {
            cin >> a[i].u >> a[i].v >> a[i].w;
        }
        sort(a + 1, a + m + 1, cmp);
        for (i64 i = 1; i <= m; i++) {
            i64 x = F(a[i].u), y = F(a[i].v);
            if (x == y) {
                if (edge[x] < note[x]) edge[x]++, ans += a[i].w;
            } else {
                if (edge[x] < note[x] || edge[y] < note[y]) {
                    Fa[x] = y;
                    edge[y] += edge[x] + 1;
                    note[y] += note[x];
                    ans += a[i].w; 
                }
            }
        } 
        cout << ans << '\n';
    }
    return 0;
}

T3

树形 DP 我是真不会啊。