总结

炸大分

T1

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

CPP

#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

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

CPP

#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 我是真不会啊。

cnt2_i

表示

2

对

i

的贡献，

cnt5_i

表示

5

对

i

的贡献。对于

x

分开计算贡献，在子树内，LCA 必定为

x

，答案为

cnt_x \times sz_x

；在 x 的子树外，必定在他的祖先上，这部分的答案直接从父亲继承再加上以父亲为答案的贡献，答案为

cnt_{fa} * (sz_{fa} - sz_x)

。最终答案讲

2

，

5

取最小值。

CPP

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

using namespace std;

const int kMaxN = 2e5 + 5;

int c2[kMaxN], c5[kMaxN], sz[kMaxN], f2[kMaxN], f5[kMaxN], ans[kMaxN], n, q;
vector<int> G[kMaxN];

int C2(int x, int ret = 0) {
	for (; x % 2 == 0; x /= 2, ret++);
	return ret;
}

int C5(int x, int ret = 0) {
	for (; x % 5 == 0; x /= 5, ret++);
	return ret;
}

void dfs(int x, int fa) {
	sz[x] = 1;
	for (auto v : G[x]) if (v != fa) {
		dfs(v, x), sz[x] += sz[v];
	}
}

void dfs1(int x, int fa) {
	f2[x] = f2[fa] + c2[fa] * (sz[fa] - sz[x]);
	f5[x] = f5[fa] + c5[fa] * (sz[fa] - sz[x]);
	ans[x] = min(f2[x] + c2[x] * sz[x], f5[x] + c5[x] * sz[x]);
	for (auto v : G[x]) if (v != fa) {
		dfs1(v, x);
	}
}

signed main() {
	cin >> n >> q;
	for (int i = 1; i <= n; i++) c2[i] = C2(i), c5[i] = C5(i);
	for (int i = 1; i < n; i++) {
		int x, y; cin >> x >> y;
		G[x].push_back(y), G[y].push_back(x);
	}
	dfs(1, 0), dfs1(1, 0);
	for (int i = 1; i <= q; i++) {
		int x; cin >> x;
		cout << ans[x] << '\n';
	} 
	return 0;
}

T4

数据很小，可以状压。

首先考虑一批一批的选数字，从

0

开始选。

考虑一个链的情况，发现选的是独立集（不能相邻）。放到树上，即是邻居不能重复选，

g_i

表示状压

i

的邻居，

w_i

表示在状压的

i

状态下的所有邻居。转移的时候枚举子集，判断并累加答案。

CPP

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

using namespace std;

const int kMaxN = 20;

int w[1 << kMaxN], f[1 << kMaxN], g[1 << kMaxN], n, m;

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v, u--, v--;
        g[u] |= 1 << v, g[v] |= 1 << u;
    }
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) w[i] |= g[j];
        }   
    }
    f[0] = 1;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = i; j; j = i & (j - 1)) {
            if ((w[j] & j) == 0 && ((w[j] & (i ^ j)) == (i ^ j)))  {
                f[i] += f[i ^ j];
            }
        }
    }
    cout << f[(1 << n) - 1] << '\n';
    return 0;
}

20250817 LiveDream 模拟赛总结

文章操作

总结

T1

T2

T3

T4

相关推荐

评论

20250817 LiveDream 模拟赛总结