Educational Codeforces Round 110 ABCDE 题解 (Java/C++)

A. Fair Playoff

题解

直接看看两组人里的胜者是不是排序后最大的两个即可。

代码

Java

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

C++

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

B. Array Reodering

题解

显然的贪心。将偶数的放在尽可能前面。因为只有在后面的数才有机会乘以2。
排好序之后直接暴力计算GCD即可。

代码

Java

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

C++

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

C. Unstable String

其实就是0101…和1010…两种方式去找最长的unstable的子串。然后再把算重复的问号给去除掉就好。

Educational Codeforces Round 110 Unstable String 题解 (Java/C++)
题解首先,我们考量本身就是unstable的串能够拆成多少个字串。对于010101。我们发现,可以拆成6个长度为1的,5个长度为2的,……,以及1个长度为6的unstable子串。因此可得,对于任意长度为n的unstable串,可以有$\frac{n\cdot(n+1)}{2}$种解。
点击上面链接查看详细题解

D. Playoff Tournament

有点线段树的那个意思。维护每场比赛的状态以及其子树里所有可能的总数即可。

Educational Codeforces Round 110 Playoff Tournament 题解 (Java/C++)
题解类似于线段树。维护当前比赛以及其前面的比赛的所有可能。以样例为例,初始状态为:
点击上面链接查看详细题解

E. Gold Transfer

就是纯的二分。但是因为是交互式的题目。因此Java实在太慢了,最后只有C++的AC代码。

Educational Codeforces Round 110 Gold Transfer 题解 (C++ only)
题解首先,因为子节点的cost一定高于其父亲节点。因此显而易见的,我们会优先选择深度更低的节点。于是我们立刻想到要快速的找到深度最浅且仍有剩余黄金的节点。于是我们很自然的想到二分的方式。以一个深度为9的节点为例,倍增的建立一个其祖先节点的位置:
点击上面链接查看详细题解