2024牛客暑期多校训练营6 题解
# A - Cake
# Question
两个人玩游戏，游戏分两阶段
第一阶段在一棵有根树上轮流走，走到叶子停止，有根树边上有 标记，记录下走过的 串（Grammy 先走）
第二阶段分蛋糕，Oscar 按自己的意愿切蛋糕，然后按照第一阶段获得的 串顺序依次拿蛋糕（ 代表 Grammy 拿， 代表 Oscar 拿）
两人都想让自己获得尽量多的蛋糕，求最后 Grammy 获得的蛋糕比例
# Solution
首先考虑第二阶段，Oscar 的最优方案是选择一个 占比最大的前缀 ，将蛋糕切成 个 大小的块，然后自己拿走 的占比那么多
所以对于第一阶段，Oscar 的目标是经过前缀 占比尽量大的点，Grammy 的目标是经过前缀 占比尽量小的点
具体怎么 DP，定义 表示从起点到 节点的 串中， 占比最大的前缀的比例，这个可以用一个从父节点到子节点的 dfs 来解决
然后定义 表示走到 ，现在要走这个人按照最优走法的最大前缀 的占比，显然，当 没有叶子节点时， ，然后我们可以按照深度来算出当前这个节点时谁走，如果是 Oscar 走，那么他肯定往最大的 走，如果是 Grammy 走，那么他肯定往最小的 走，这个可以用一个从叶子到根节点的 DP 来解决
# Code
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n; cin >> n;
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 1; i < n; i++) {
int u, v, w; cin >> u >> v >> w;
g[u].push_back({v, w}); g[v].push_back({u, w});
}
vector<int> dep(n + 1); dep[1] = 1;
vector<double> f(n + 1); f[1] = 0; // f 表示前缀 0 的最大占比
vector<array<int, 2>> cnt(n + 1); cnt[0] = {0, 0};
function<void(int, int)> dfs1 = [&] (int u, int fa) {
if (u != 1)
f[u] = max(1.0 * f[u], 1.0 * cnt[u][0] / (cnt[u][0] + cnt[u][1]));
for (auto [v , w] : g[u]) {
if (v == fa) continue;
dep[v] = dep[u] + 1;
cnt[v] = cnt[u]; cnt[v][w] += 1;
f[v] = f[u];
dfs1 (v, u);
}
};
vector<double> dp(n + 1); // dp 表示走到 u 的最优解
function<void(int, int)> dfs2 = [&] (int u, int fa) {
if (dep[u] & 1) dp[u] = 1;
else dp[u] = 0;
int flg = 0;
for (auto [v, w] : g[u]) {
if (v == fa) continue;
dfs2(v, u);
flg = 1;
if (dep[u] & 1) dp[u] = min(dp[u], dp[v]);
else dp[u] = max(dp[u], dp[v]);
}
if (!flg) dp[u] = f[u];
};
dfs1(1, 0);
dfs2(1, 0);
cout << fixed << setprecision(10) << 1 - dp[1] << '\n';
}
int main() {
freopen ("A.in", "r", stdin);
ios::sync_with_stdio(0);
int T; cin >> T;
while (T--) solve();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# B - Cake 2
# Solution
自己多花几个，然后就能找到规律，
当然要特别考虑 的情况
# Code
#include <bits/stdc++.h>
using namespace std;
int main() {
long long N, K; cin >> N >> K;
if (N % 2 == 0 && K == N / 2) {
cout << N << endl;
}
else if (K > N / 2) {
K = N - K;
cout << N * K + 1 << endl;
}
else {
cout << N * K + 1 << endl;
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# D - Puzzle: Wagiri
# Question
给定一张简单连通无向图，边有黑白，移除任意多条边使得图仍然连通，且黑边都在环上，白边都不在环上，或输出无解
# Solution
保留所有黑边，做边双连通分量
然后去掉所有桥边，使用白边将原本不连通的连通块连起来，就是做一个 MST
如果最终得到的图连通，则已经获得了一个解，否则无解
# Code
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int main() {
ios::sync_with_stdio(false);
int n, m; cin >> n >> m;
vector<vector<int>> g(n + 1);
map<pii, int> mp, mp2;
for (int i = 1; i <= m; i++) {
string s; int u, v, w; cin >> u >> v; cin >> s;
w = (s == "Lun");
if (w == 1) {
mp[{u, v}] = 1;
g[u].push_back(v); g[v].push_back(u);
}
else {
mp2[{u, v}] = 1;
}
}
vector<int> dfn(n + 1, 0), low(n + 1, 0); int dfn_cnt = 0;
vector<pair<int, int>> cut_bridge;
function<void(int, int)> tarjan = [&] (int u, int fa) {
dfn[u] = low[u] = ++dfn_cnt;
for (auto v : g[u]) {
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
if (low[v] > dfn[u]) cut_bridge.push_back({u, v});
}
else if (v != fa) low[u] = min(low[u], dfn[v]);
}
};
for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
for (auto [u, v] : cut_bridge) {
mp.erase({u, v}); mp.erase({v, u});
}
vector<int> fa(n + 1);
iota(fa.begin(), fa.end(), 0);
function<int(int)> find = [&] (int x) -> int {
return x == fa[x] ? x : fa[x] = find(fa[x]);
};
for (auto [x, _] : mp) {
auto [u, v] = x;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fu] = fv;
}
for (auto [x, _] : mp2) {
auto [u, v] = x;
int fu = find(u), fv = find(v);
if (fu == fv) continue;
fa[fu] = fv;
mp[{u, v}] = 1;
}
vector<int> hsh(n + 1, 0);
for (int i = 1; i <= n; i++) hsh[find(i)]++;
int cnt = 0;
for (int i = 1; i <= n; i++) cnt += (hsh[i] > 0);
if (cnt > 1) { cout << "NO" << endl; return 0;}
cout << "YES" << '\n';
cout << mp.size() << '\n';
for (auto [u, v] : mp) {
cout << u.first << ' ' << u.second << '\n';
}
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# F - Challenge NPC 2
# Question
给定一颗森林，求其补图的哈夫曼路径
# Solution
考虑到一层中的点在原图中是没有边的，说明其在补图中是有边的，所以对于一层的节点，是可以一串处理掉的
然后考虑如何链接不同层，很容易想到的方法就是奇偶链接：，然后把 和 连，这样子就全部串在一起了
考虑无解的情况，就是一个菊花图
如果最深的深度小于
- 如果为 说明都是单点，串起来即可
- 如果为 ，如果只有一颗树无解，如果有多棵树，则分层串
- 如果为 ，还是奇偶分层，然后找一个 且 直接没有连边的 ，把他们在补图中作为哈夫曼路径即可
具体实现还是挺恶心的
# Code
#include <bits/stdc++.h>
using namespace std;
void solve() {
int n, m; cin >> n >> m;
vector<int> dep(n + 1, 0), rt(n + 1, 0);
vector<vector<int>> g(n + 1);
for (int i = 1; i <= m; i++) {
int u, v; cin >> u >> v;
g[u].push_back(v); g[v].push_back(u);
}
vector<int> root;
function<void(int, int, int, int)> dfs = [&](int u, int fa, int d, int r) {
dep[u] = d; rt[u] = r;
for (auto v : g[u]) {
if (v == fa) continue;
dfs(v, u, d + 1, r);
}
};
for (int i = 1; i <= n; i++) {
if (dep[i] != 0) continue;
root.push_back(i);
dfs(i, 0, 1, i);
}
int max_dep = *max_element(dep.begin() + 1, dep.end()); // max_dep 表示最深的深度
if (max_dep == 1) {
for (int i = 1; i <= n; i++) cout << i << ' ';
cout << '\n';
return ;
}
if (root.size() > 1) {
int x, y;
for (int i = 1; i <= n; i++) if (dep[i] == 2) x = i;
for (int i = 1; i <= n; i++) if (dep[i] == 1 && rt[i] != rt[x]) y = i;
for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
cout << y << ' ' << x << ' ';
for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
cout << '\n';
}
else {
if (max_dep == 2) {
cout << "-1" << '\n';
}
else if (max_dep == 3) {
int x, y;
vector<int> v;
for (int i = 1; i <= n; i++) if (dep[i] == 2) v.push_back(i);
if (v.size() == 1) {
cout << "-1" << '\n';
}else {
int x, y;
for (int i = 1; i <= n; i++) if (dep[i] == 3) y = i;
for (auto u : v) {
bool flg = 1;
for (auto v : g[u]) {
if (v == y) {flg = 0; break;}
}
if (flg) {x = u; break;}
}
for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
cout << y << ' ' << x << ' ';
for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
cout << '\n';
}
}
else {
int x, y;
for (int i = 1; i <= n; i++) {
if (dep[i] == 1) x = i;
if (dep[i] == 4) y = i;
}
for (int i = 1; i <= n; i++) if ((dep[i] & 1) && i != y) cout << i << ' ';
cout << y << ' ' << x << ' ';
for (int i = 1; i <= n; i++) if ((dep[i] & 1) == 0 && i != x) cout << i << ' ';
cout << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
while (T--) solve();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# H - Genshin Impact's Fault
# Solution
签到题
# Code
#include <bits/stdc++.h>
using namespace std;
bool check1 (string s) {
int n = s.size(); s = " " + s;
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++)
sum[i] = sum[i - 1] + (s[i] == '3');
for (int l = 1; l + 10 - 1 <= n; l++) {
int r = l + 10 - 1;
if (sum[r] - sum[l - 1] == 10) return false;
}
return true;
}
bool check2(string s) {
int n = s.size(); s = " " + s;
vector<int> sum(n + 1, 0);
for (int i = 1; i <= n; i++) {
if (s[i] == '5' || s[i] == 'U') sum[i] = sum[i - 1] + 1;
else sum[i] = sum[i - 1];
}
for (int l = 1; l + 90 - 1 <= n; l++) {
int r = l + 90 - 1;
if (sum[r] - sum[l - 1] == 0) return false;
}
return true;
}
bool check3 (string s) {
char lst = ' ';
for (auto ch: s) {
if (ch == 'U' || ch == '5') {
if (lst == '5' && ch == '5') return false;
lst = ch;
}
}
return true;
}
void solve() {
string s; cin >> s;
bool res = check1(s) && check2(s) && check3(s);
cout << (res ? "valid" : "invalid") << '\n';
}
int main() {
ios::sync_with_stdio(false);
int T; cin >> T;
while (T--) solve();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# I - Intersecting Intervals
# Question
给定一个数字矩阵，每一行选择一个区间，要求相邻行的区间有交，求最大化选中的数字和
# Solution
有点类似于最大子段求和，但是这里是多行的
定义 表示前 行，强制选择 的最优答案
那么转移就需要枚举上一行选择的数字 并且保证上一行和这一行有交
那么转移方程就是
其中 表示以 结尾的最长子序列大小， 表示以 开头的最长子序列大小
此时的转移是 ，但是这里可以使用前缀/后缀 优化转移，时间复杂度为
具体实现就是定义一个数组 表示
那么对于 的转移就是 ， 也是同理
# Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve() {
int n, m; cin >> n >> m;
vector<vector<ll>> a(n + 5, vector<ll>(m + 5, 0));
vector<vector<ll>> dp(n + 5, vector<ll>(m + 5, 0));
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
for (int i = 1; i <= n; i++) {
vector<ll> pre(m + 5, 0), pre_max(m + 5, 0), suf(m + 5, 0), suf_max(m + 5, 0);
for (int j = 1; j <= m; j++) {
pre[j] = max(pre[j - 1] + a[i][j], a[i][j]);
if(j == 1) pre_max[j] = pre[j] + dp[i - 1][j];
else pre_max[j] = max(pre_max[j - 1] + a[i][j], pre[j] + dp[i - 1][j]);
}
for (int j = m; j >= 1; j--) {
suf[j] = max(suf[j + 1] + a[i][j], a[i][j]);
if(j == m) suf_max[j] = suf[j] + dp[i - 1][j];
else suf_max[j] = max(suf_max[j + 1] + a[i][j], suf[j] + dp[i - 1][j]);
}
for (int j = 1; j <= m; j++) {
dp[i][j] = max(pre[j] + suf_max[j], pre_max[j] + suf[j]) - a[i][j];
}
}
ll ans = *max_element(dp[n].begin() + 1, dp[n].end());
cout << ans << '\n';
}
int main() {
freopen ("I.in", "r", stdin);
ios::sync_with_stdio(false);
int T; cin >> T;
while (T--) solve();
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
上次更新: 2025/04/08, 18:03:31