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

A. Computer Game

题解

从左往右依次扫描即可。只要左边一列中有一个可以被访问,则当前列的所有安全的cell都可以被访问。

代码

Java

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

C++

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

B. Groups

题解

枚举上课的是哪两天。只要这两天能让所有人都有课上,且每个课能来上课的人超过一半,就一定能够找到一种划分的方法。
考虑最坏的情况,某一天能来的那一半人都只能在那一天来。那么根据上面的条件,剩下的那一半人一定在另外一天。

代码

Java

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

C++

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

C. Delete Two Elements

题解

令原数组的所有元素和为sum,删除的两个数分别为x和y。那么根据题意,必然有$\frac {sum} n = \frac {sum - x -y} {n-2}$。于是自然的有$sum \cdot (n-2) = (sum - x -y) \cdot n$。

显然x+y的值是一个定值。因此随着x的增大,y必然减小。于是我们对原数组进行排序,依次枚举x即可。
而枚举过程中唯一需要注意的是,原数组可能存在相同的元素,因此我们需要统计每个数字出现的次数,并且对原数组去重。

代码

Java

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

C++

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

D. Training Session

题解

考虑两个条件都不符合的组合是什么样的。不难想到,想要两个条件都不满足,三道题目的difficult或者topic不能都一样。
以三道题topic都一样为例,根据题目定义,此时三道题difficult必然都不一样。因此必然符合其中一个条件。

于是,difficult和topic都有且只有两个题目一样。举个例子:

显然,根据上图,三道题目中必然有一道difficult和topic都是红色。而另外两个题目中,有且只有一道题目的topic是红色,另一道题目的difficult是红色。

于是我们枚举这道topic和difficult都是红色的题目即可。

代码

Java

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

C++

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

E. Staircases

题解

首先我们发现,每个格子都恰好可以被映射到两个楼梯内。以下图*的格子为例,可以被映射到下面两个楼梯:

类似的,对于对角线下方的点也可以映射到两个楼梯内:

于是就很显然了。当我们改变一个格子的时候,这个格子的影响只会波及往上和往下第一个已经锁住的格子(也就是只和最长连续楼梯有关)。以下图为例:

如果我们要把*的锁住,其产生的影响是5*3=15个不同的楼梯,也就是往上的任意一个格子,到往下的任意一个格子(包括*的格子)。

把锁住的格子解锁也是同理。

代码

Java

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

C++

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

最近工作太忙,F题实在来不及看。

展示评论