我是靠谱客的博主 义气方盒,这篇文章主要介绍Educational Codeforces Round 120 (Rated for Div. 2) (A-C) 题解,现在分享给大家,希望可以做个参考。

完整代码:https://github.com/abmcar/ACM/tree/master/OpenjudgeNow/Codeforces/Educational%20Codeforces%20Round%20120%20(Rated%20for%20Div.%202)
更好的阅读体验:
http://www.abmcar.top/archives/educationalcodeforcesround120ratedfordiv2

A. Construct a Rectangle在这里插入图片描述

题目大意:给你三根木棍,你可以把其中一根劈成2根正整数长度的木棍,问这四根木棍是否能够组成矩形.
思路:能组成矩形的大致分为两类,一类两边做临边,一类做对边
第一类,我们判断是否有两根木棍的长度相同且另一根可以被分成2半
第二类,判断是否第三根长度等于其余两根
代码:

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
void work() { cin >> num[1] >> num[2] >> num[3]; if (num[1] + num[2] == num[3] || num[1] + num[3] == num[2] || num[2] + num[3] == num[1]) cout << "Yes" << Endl; else if ((num[1] == num[2] && num[3] % 2 == 0) || (num[1] == num[3] && num[2] % 2 == 0) || (num[2] == num[3] && num[1] % 2 == 0)) cout << "Yes" << Endl; else cout << "NO" << endl; }

B. Berland Music

在这里插入图片描述
题目大意:给你n首歌曲,并给你它们的预测分(或者说排名),之后给你一串01串表示喜欢或者不喜欢,让你给分使得所有喜欢的歌曲的分数大于不喜欢的,并且你给的分和预测分的差最小
思路:已知每个分数只出现一次,采取贪心的思想,对于某两个喜欢的歌曲a,b若原分数Pa < Pb,则给定的分数也应该是Qa < Qb,不喜欢同理,因此我们对原分数排序,按照喜欢还是不喜欢排名,之后按照不喜欢-喜欢的顺序给排名赋分
代码:

复制代码
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
struct Node { int pos, val; bool operator<(Node b) { return val < b.val; } }; void work() { cin >> n; vector<int> rat(n + 1); for (int i = 1; i <= n; i++) cin >> rat[i]; String s; cin >> s; vector<Node> dislike, like; for (int i = 0; i < n; i++) if (s[i] == '0') dislike.push_back({i + 1, rat[i + 1]}); else like.push_back({i + 1, rat[i + 1]}); vector<int> ans(n + 1); sort(dislike.begin(), dislike.end()); sort(like.begin(), like.end()); for (int i = 0; i < dislike.size(); i++) ans[dislike[i].pos] = i + 1; for (int i = 0; i < like.size(); i++) ans[like[i].pos] = dislike.size() + i + 1; for (int i = 1; i <= n; i++) cout << ans[i] << " "; cout << endl; }

C. Set or Decrease

在这里插入图片描述
题目大意:
给你一个数组和一个k
你可以每次选择
使数组中的一个元素-1
或者 让数值中的一个元素等于另一个元素
问最少多少次操作是的数组和小于k
思路:
显然赋值操作应该在减操作后执行,因此,应当选择最小的一个数来进行操作1,之后对于大的数进行操作2
我们发现,如果固定赋值操作的个数,我们可以快速求出应该进行多少次操作1
假如我们枚举操作2的个数i,我们知道有(n-i-1)个数不会被改变,数组中比较大的i个数会被赋值,可以用前缀和求出这(n-i-1)个数的和 nowTot = k-(preAsn[i]-nums[1]),其中preAns为前缀和,nums为排序过的数组,之后求这些数的单个值nowLess = nowTot /(n - i - 1),之后处理余数,本次的ans = (num[1]-nowLess + n - i )

代码:

复制代码
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
void work() { cin >> n >> k; vector<int> nums(n + 1), preAns(n + 1); ll ans = 1e18; for (int i = 1; i <= n; i++) cin >> nums[i]; sort(nums.begin() + 1, nums.begin() + 1 + n); for (int i = 1; i <= n; i++) preAns[i] = preAns[i - 1] + nums[i]; for (int i = n; i >= 1; i--) { ll nowTot = preAns[i] - nums[1]; nowTot = k - nowTot; ll nowCnt = 1 + (n - i); ll nowLess = nowTot / nowCnt; // 处理余数 while (nowLess * nowCnt > nowTot) nowLess--; // nowLess = max(nowLess, 0LL); ll nowAns = max(0LL,nums[1] - nowLess) + (n - i); ans = min(ans, nowAns); // cout << i << " " << nowCnt << " " << nowLess << " " << nowAns << endl; } ans = max(0LL, ans); cout << ans << endl; }

最后

以上就是义气方盒最近收集整理的关于Educational Codeforces Round 120 (Rated for Div. 2) (A-C) 题解的全部内容,更多相关Educational内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(84)

评论列表共有 0 条评论

立即
投稿
返回
顶部