Educational Codeforces Round 114 ABCD 题解 (Java/C++)

A. Regular Bracket Sequences

题解

以n=5为例,我们可以立刻写出1种解法:()()()()()。

接着我们可以写出下面4种解法:
(())()()()()
()(())()()()
()()(())()()
()()()()(())

代码

Java

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

C++

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

B. Combinatorics Homework

题解

显然,我们是可以找出m的最大最小值的。而且我们可以通过调换顺序来获得最大最小的值之间的任意的m。

考虑m的最大值:不难发现我们按aaaabbbbcccc这样排列时m最大。因此m的最大值为a-1+b-1+c-1。

接着考虑m的最小值:这里不妨假设a的数目最多。那么也不难发现,按ababacacaaaa这样排列时m最小,于是m的最小值为a-b-c-1。

代码

java

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

C++

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

C. Slay the Dragon

题解

我们发现,不论是攻击或是防御,两种行动都是靠勇士的力量来完成的。

因此不难想到,最优解应当尽可能避免防御力量或者攻击力量溢出。比如攻击力量溢出太多的时候,相应的就可能需要花更多金币来补充防御力量。

于是我们只需要根据x,找到力量最接近x的两个勇士分别计算相应的开销去最小值即可。

代码

Java

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

C++

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

D. The Strongest Build

题解

因为m最多只有$10^5$,因此直接暴力枚举前$10^5$种可能即可。

我们用一个优先队列来对维护各种可能,把力量最高的排在前面。我们首先将最大的可能加入队列。然后如果队首的结果被ban了,就把这个结果相应的n种较小的结果加入队列。

这样最多ban$10^5$次就能得到答案。

代码

Java

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

C++

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