偶遇神秘重庆，写五个签到（？）
补题链接
铁：B, E, I, J, K
铜：C
银：D, A
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;
}
|
显然我觉得 Python 写这种有精度需求的东西是正确的。
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
| from decimal import Decimal, ROUND_HALF_UP, getcontext
def main():
import sys
data = sys.stdin.read().split()
t = int(data[0])
index = 1
results = []
getcontext().prec = 10
for _ in range(t):
ppmax = Decimal(data[index]); index += 1
a = Decimal(data[index]); index += 1
b = Decimal(data[index]); index += 1
c = Decimal(data[index]); index += 1
d = Decimal(data[index]); index += 1
e = Decimal(data[index]); index += 1
f_val = Decimal(data[index]); index += 1
acc = Decimal('300') * a + Decimal('300') * b + Decimal('200') * c + Decimal('100') * d + Decimal('50') * e
suma = a + b + c + d + e + f_val
suma *= Decimal('3')
pp = Decimal('320') * a + Decimal('300') * b + Decimal('200') * c + Decimal('100') * d + Decimal('50') * e
sumb = a + b + c + d + e + f_val
sumb *= Decimal('320')
percentage_a = (acc / suma)
temp_sumb = pp / sumb
temp_value = max(Decimal('0'), temp_sumb - Decimal('0.8')) * Decimal('5.0') * ppmax
rounded_sumb = temp_value.quantize(Decimal('1.'), rounding=ROUND_HALF_UP)
rounded_percentage = percentage_a.quantize(Decimal('0.01'), rounding=ROUND_HALF_UP)
results.append(f"{rounded_percentage:.2f}% {rounded_sumb:.0f}")
for result in results:
print(result)
if __name__ == "__main__":
main()
|
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$ 的卡片上。
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
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using f64 = double;
constexpr int modn = 998244353;
void solve() {
array<i64, 11> a = {};
for (int i = 1; i <= 9; i++) {
cin >> a[i];
}
if (a[1] > 0 and a[2] > 0) {
int m = min(a[1], a[2]);
a[3] += m;
a[1] -= m;
a[2] -= m;
}
while (a[1] > 4 or a[1] == 3)
a[1] -= 3, a[3]++;
if (a[1]) {
a[2] += a[1] / 2;
a[1] %= 2;
}
for (int i = 2; i <= 9; i++) {
if (a[1] and a[i]) {
a[1]--, a[i]--, a[i + 1]++;
break;
}
}
i64 ans = 1;
for (int i = 1; i <= 10; i++) {
while (a[i]--) {
(ans *= i) %= modn;
}
}
cout << ans << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T;
cin >> T;
while (T--)
solve();
return 0;
}
|
J. 骰子
最签到。
给定一个骰子，你可以沿边转动它，并按下它底面的数字到下面的 $n\times m$ 个格子上。问格子上所有数字的和的最大值。
手玩一下不难发现只要 $n,m$ 大于 $2$ 就能让每一个格子都印上 $6$，题目给定 $2 \le n, m$，因此直接输出 $2 \times n \times m$ 即可。
1
2
3
4
5
6
7
8
9
10
11
12
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
i64 n, m;
cin >> n >> m;
cout << 6 * (n * m) << "\n";
return 0;
}
|
K . 小 C 的神秘图形
坏了，这个题解跨度太长了，有点忘了。
题目太长，略
我们首先打一个表就不难发现，当且仅当 $a_i=b_i=1$ 对于每一个 $i\in[1,n]$ 时会有答案为 $1$，否则答案为 $0$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using f64 = double;
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int n;
cin >> n;
string a, b;
cin >> a >> b;
for (int i = 0; i < n; i++) {
if (a[i] != '1' and b[i] != '1') {
cout << "0\n";
return 0;
}
}
cout << "1\n";
return 0;
}
|
以上为铁牌
C. 连方
给定正整数 $n$ 和两个只包含 . 和 # 的长度为 $n$ 的字符串 $a, b$，构造一个 $7\times n$ 的仅包含字符 . 和 # 的矩阵，满足：
- 第 $1$ 行与 $a$ 相同，第 $7$ 行与 $b$ 相同。
- 四方向连通的
# 块都是实心矩形。 - 八方向
# 块都连通。
输出一个满足条件的矩阵或者判定无解。
一个比较显然的想法就是对于单行的 # 来说它本来就是矩形，所以我们只需要在第二行和倒数第二行把第一行和倒数第一行取反就行，剩下的三行我们想办法让它能八连通就可以了。注意一些边界情况，比如第一行满最后一行空就不可能有解。
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
| #include <bits/stdc++.h>
using namespace std;
void solve() {
int n;
cin >> n;
array<string, 7> g = {};
cin >> g.front();
cin >> g.back();
g[1] = g[0];
int c1 = 0, c7 = 0;
for (auto &x : g[1]) {
if (x == '.')
x = '#';
else
x = '.', c1++;
}
g[5] = g[6];
for (auto &x : g[5])
if (x == '.')
x = '#';
else
x = '.', c7++;
if (c1 == n and c7 != n or c1 != n and c7 == n) {
cout << "No\n";
return;
}
cout << "Yes\n";
if (c1 == n and c7 == n) {
for (int i = 0; i < 7; i++) {
for (int j = 0; j < n; j++)
cout << "#";
cout << "\n";
}
return;
}
g[2] = g[3] = g[4] = string(n, '.');
int l = -1, r = -1;
for (int i = 0; i < n; i++) {
if (g[1][i] == '#')
continue;
if (i - 1 >= 0 and g[1][i - 1] == '#' or i + 1 < n and g[1][i + 1] == '#')
l = i;
}
for (int i = 0; i < n; i++) {
if (g[5][i] == '#')
continue;
if (i - 1 >= 0 and g[5][i - 1] == '#' or i + 1 < n and g[5][i + 1] == '#')
r = i;
}
g[2][l] = g[4][r] = '#';
if (l > r)
swap(l, r);
if (l == r or l + 1 == r)
g[3][l] = '#';
else {
for (int i = l + 1; i < r; i++)
g[3][i] = '#';
}
for (int i = 0; i < 7; i++)
cout << g[i] << "\n";
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|