CF Global Round 14 题解

[toc]

AC代码

A. Phoenix and Gold

给定 $N$ 个不同权值的物品和一个整数 $x$，物品的权值分别为 $w_i$，能否给出一种 $w_i$ 的排列使得不存在 $j$ 使得 $\sum_{i=0}^{j}w_i=x$ 。

至多 $1000$ 组询问，$n\leq 100,1\leq w_i\leq 100$ 。

由于物品权值各不相同，因此只要 $x\neq \sum_{i=0}^{n-1}w_i$ 就一定有解。构造很简单，直接扫一遍数列检查是否存在前缀和为 $x$ ，若存在则交换它和后面那个就行了。

B. Phoenix and Puzzle

多组询问，询问 $N$ 块等腰直角三角形板能否拼成一个正方形。

$N\leq 10^9$ 。

画一下可以发现：正方形的最小形态只有 $N=2,4$ 这两种，因此 $N=2p^2,4p^2$ ，检查一下 $N$ 是否满足即可。

C. Phoenix and Towers

有 $N$ 个方块，高度分别为 $h_i$ ，将它们分成 $M$ 堆，每一堆方块的高度是这堆方块的高度之和，构造一种方案使得这 $M$ 堆方块中任意两堆的高度差不超过 $X$（保证 $X\geq\max(h_1,h_2,\cdots,h_n)$）。

$\sum N\leq 10^5$ 。

直接将 $h_n$ 数组排序，$0,1,2,\cdots,n-1$ 每一项 $h_i$ 丢进第 $i\% m+1$ 堆。

这是因为数组 $h_i$ 递增，因此最小堆和最大堆的差值一定不会超过 $h_{n-1}-h_0\leq X$ 。

D. Phoenix and Socks

有 $N$ 只袜子，其中 $L$ 只是左脚的，$R$ 只是右脚的，每只袜子都有一个颜色 $c_i$ 。你可以花费 $1$ 点代价将左脚翻转为右脚或者右脚翻转为左脚的袜子，也可以花费 $1$ 点代价改变袜子的颜色。任意两只分别为左、右脚且颜色相同的袜子可以配对，询问最小的完全匹配代价。

$\sum N\leq 10^5$ 且为偶数。

从贪心的角度出发，首先可以匹配的袜子我们肯定不需要进行操作，然后仅需要翻转左右脚或者改变颜色就能配对的袜子（需要花费一点代价）我们优先匹配上，最后剩下的袜子肯定需要两点代价了。

E. Phoenix and Computers

有 $N$ 台未启动的电脑排成一列，你每次可以打开一台未启动的电脑。如果某台电脑左右两侧的电脑都启动了，那么它也会自动启动，询问一共有几种不同的开机方式使得所有电脑都启动。

$N\leq 400$ 。

看到这道题之后发现没什么想法，于是打了个表。。。瞎搞了一通之后震惊地发现这个表与第二类斯特林数有关系！然后就愉快地AC了。。。而且这个做法是 $O(N^2)$ 的，还挺优秀，代码可以查看 AC代码 。

正解有空再更吧。