Codeforces Global Round 14 ABCD 题解

A. Phoenix and Gold

题意

给你一个长度为n的数组w,其中w中没有重复数字,问可不可能有一种排列使得:对任意的i,$\sum\limits_{j = 1}^{i}w_j \ne x$

题解

如果所有数的和为x则无解。因为不论如何替换,当i=n时,和都为x。

否则,由于w中每个值都不同,所以,一旦发现原始排列的某一位的和为x,只需要和后一位交换就行了。如:1,2,3,4中x为3。只需要将2,3交换即可。

代码

Submission #114960365 - Codeforces
Codeforces. Programming competitions and contests, programming community

B. Phoenix and Puzzle

题意

给你n个等腰直角三角形,问你能不能拼出正方形。

题解

首先,我们可以看到,2个和4个都能拼出正方形。于是基于这两种正方形,往外扩展即可。

代码

Submission #114961841 - Codeforces
Codeforces. Programming competitions and contests, programming community

C. Phoenix and Towers

题意

给你n个块,高度为h。每块的高度不超过x。现在问你怎么用这n个块叠出m个塔,使任意两塔间高度差不超过x。

题解

贪心,每次找出当前高度最小的塔,往上放一块就行了。因为$h<x$,所以放了之后一定不会超过其他任意一个塔的高度x。

代码

Submission #114960434 - Codeforces
Codeforces. Programming competitions and contests, programming community

D. Phoenix and Socks

题意

你有n只袜子,其中有l只是左边的,r只是右边的。每只袜子的颜色是c。每次操作可以把一只袜子改颜色,或者把左/右袜子改成右/左袜子。问你最少多少步可以配对。

题解

不妨假设左边袜子比右边袜子少。

我们可以贪心:首先优先将左边的袜子与右边的袜子配对。然后再把右边袜子中颜色相同的拿一只到左边。最后,随便从右边拿袜子到左边,同时染色。

代码

Submission #114960470 - Codeforces
Codeforces. Programming competitions and contests, programming community