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交换即可。

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

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

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

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

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

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

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