偶遇神秘重庆，写五个签到（？）
B. osu!mania
简单模拟题，唯一需要注意的是精度问题。这里采用的处理办法是乘 $10^9$ 后四舍五入取整，然后再除以 $10^9$ 次方输出需要的即可。
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
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using f64 = double;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--) {
f64 ppmax;
cin >> ppmax;
f64 a, b, c, d, e, f;
cin >> a >> b >> c >> d >> e >> f;
f64 acc = 300 * a + 300 * b + 200 * c + 100 * d + 50 * e + 0 * f;
acc /= 300 * (a + b + c + d + e + f);
acc *= 100;
f64 pp = 320 * a + 300 * b + 200 * c + 100 * d + 50 * e + 0 * f;
pp /= 320 * (a + b + c + d + e + f);
pp = max(0.0, pp - 0.8) * 5 * ppmax;
i64 o1 = round(acc * 1e9);
i64 o2 = round(pp * 1e9);
println("{:.2f}% {:.0f}", o1 / 1e9, o2 / 1e9);
}
return 0;
}
|
E. 合成大西瓜
给定 $n$ 个节点（$n$ 是奇数）和权重 $a_i$ 和 $m$ 条无向边。每次操作可以选择三个不同的节点 $x,,y,,z$ 满足 $x,y$ 之间有一条边，$y,z$ 之间有一条边。然后得到一个新的节点 $w$，其权重为 $a_w=\max(a_y,\min(a_x,a_z))$。然后删除 $x,y,z$ 并把原有的边接到这个新的节点上。
首先我们不难看出对于所有的非叶子节点，我们可以合并成一个点，这个点的权重是所有非叶子节点的最大值。然后我们考虑一个中心点和一堆叶子节点。叶子节点对于答案的贡献只有叶子节点的次大值。因此最终的答案就是非叶子节点的最大值和叶子节点的次大值之中的最大值。
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
| #include <bits/stdc++.h>
using namespace std;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
vector adj(n + 1, vector<int>{});
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
while (m--) {
int u, v;
cin >> u >> v;
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
if (n == 1) {
cout << a[1] << "\n";
return 0;
}
int mx = -1;
int m1 = -1, m2 = -1;
for (int i = 1; i <= n; i++) {
if (adj[i].size() > 1)
mx = max(mx, a[i]);
else if (a[i] > m1) {
m2 = m1;
m1 = a[i];
} else if (a[i] > m2)
m2 = a[i];
}
cout << max(mx, min(m1, m2)) << "\n";
return 0;
}
|
I. 算数
给定写着 $1..9$ 的卡片，其中写着 $i$ 的有 $a_i$ 张。每次操作可以选择两张卡片合成一张，合成后的卡片的值可以为二者之和或之积。问所有操作后剩下的卡的最大值，并模 $998244353$ 后输出。
首先我们不难得到除了 $1$ 之外的卡片最好的操作都是乘起来。然后考虑所有为 $1$ 的卡牌，可以选 $x$ 张卡片合成为 $x$，或者把 $1$ 加到某张卡片上。
我们记现在的值为 $a$ 有 $n$ 张卡片，要合成为 $x$，那么合成后相乘的值为 $a \times x^{\lfloor n / x \rfloor}$，如果不合成直接相加的值为 $a+n$。然后我们不难找到极值 $x=\mathrm{e}$ 使得合成功效最大化。因此我们需要尽可能地把 $1$ 变成 $3$。
首先如果我们当前有 $2$ 的话把 $2$ 加成 $3$，否则用三个 $1$ 合成 $3$，这里需要注意有四个 $1$ 的情况手玩可得合成 $2$ 比较好。剩下如果有两个 $1$ 就合成为 $2$，否则就把这个 $1$ 加到最小的不是 $1$ 的卡片上。