Acwing 第 85 场周赛
摘要
Title: Acwing 第 85 场周赛
Tag: 贪心、并查集
Powered by:NEFU AB-IN
Acwing 第 85 场周赛
-
A AcWing 4791. 死或生
-
题意
略
-
思路
模拟即可
-
代码
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
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
int n, cnt11, cnt12, cnt21, cnt22;
signed main()
{
IOS;
cin >> n;
for (int i = 1; i <= n; ++i)
{
int t, x, y;
cin >> t >> x >> y;
if (t == 1)
cnt11 += x, cnt12 += y;
else
cnt21 += x, cnt22 += y;
}
if (cnt11 >= cnt12)
cout << "LIVE\n";
else
cout << "DEAD\n";
if (cnt21 >= cnt22)
cout << "LIVE\n";
else
cout << "DEAD\n";
return 0;
}
-
-
B AcWing 4792. 最大价值
-
题意
已知，小写字母 a∼z的价值分别为 wa,wb,…,wz
对于一个由小写字母构成的长度为 l的字符串 S=s1s2…sl，其价值为 ws1×1+ws2×2+…+wsl×l
现在，给定一个由小写字母构成的字符串 S，请你在这个字符串中插入 k 个小写字母，要求最终得到的字符串的价值尽可能大。
输出最大可能价值。 -
思路
贪心 (当时未证明)，思路是将k个w最大的放在最后面即可
-
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-02 18:39:23
* @FilePath: \Acwing\85cp\b\b.cpp
* @LastEditTime: 2023-02-02 19:09:55
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
string s;
int k, mx;
unordered_map<char, int> mp;
signed main()
{
IOS;
cin >> s >> k;
for (char i = 'a'; i <= 'z'; ++i)
{
int x;
cin >> x;
mp[i] = x;
mx = max(mx, x);
}
int ans = 0;
for (int i = 0; i < SZ(s); ++i)
{
ans += (i + 1) * mp[s[i]];
}
// DEBUG(ans);
for (int i = SZ(s) + 1; i < SZ(s) + 1 + k; ++i)
{
ans += i * mx;
}
cout << ans;
return 0;
}
-
-
C AcWing 4793. 危险程度
-
题意
有 n种化学物质，编号 1∼n
其中，有 m对物质之间会发生反应。
现在，要将这些化学物质逐个倒入同一个试管之中，具体倒入顺序不限。
我们需要计算一下试管的危险值。
已知，空试管的危险值为 1，每倒入一种化学物质，如果该物质能够与之前倒入试管中的一种或多种物质发生反应，则试管的危险值将乘以 2
请你计算并输出，通过合理安排所有化学物质的倒入顺序，能够得到的试管的最大危险值。 -
思路
思路：找所有的连通块，每个连通块的祖先节点放入试管时，试管是不乘2的，其余情况都乘2
-
代码
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/*
* @Author: NEFU AB-IN
* @Date: 2023-02-02 18:39:23
* @FilePath: \Acwing\85cp\b\b.cpp
* @LastEditTime: 2023-02-02 19:09:55
*/
using namespace std;
typedef pair<int, int> PII;
const int N = 1e5 + 10, INF = 0x3f3f3f3f;
string s;
int k, mx;
unordered_map<char, int> mp;
signed main()
{
IOS;
cin >> s >> k;
for (char i = 'a'; i <= 'z'; ++i)
{
int x;
cin >> x;
mp[i] = x;
mx = max(mx, x);
}
int ans = 0;
for (int i = 0; i < SZ(s); ++i)
{
ans += (i + 1) * mp[s[i]];
}
// DEBUG(ans);
for (int i = SZ(s) + 1; i < SZ(s) + 1 + k; ++i)
{
ans += i * mx;
}
cout << ans;
return 0;
}
-