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

A. Balanced Substring

题解

只需要找到"ab"或者"ba"即可。

代码

Java

C++

B. Chess Tournament

题解

对于一场也不想输的人，我们就让他们一直平局就好。

剩下想要至少赢一场的，只要能构成一个环即可。需要注意的是，2个人也是不能成环的。

代码

Java

C++

C. Jury Meeting

题解

我们找出任务数最多的人。

首先，如果有多个人，都具有最多的任务数。那么显而易见的，无论怎么排列都能满足条件。直接输出n!即可。

如果任务数最多的人比任务数第二多的人多出了超过2个任务（包括两个），那么显而易见，一定是无解的。

于是，我们就只剩下一种情况：一个任务数最多的人，若干任务数第二多的人，以及其他人。
对于这种情况，我们只要保证这个任务数最多的人后面至少有一个任务数第二多的人即可。
最后，把其他人插入任务数最多的人和任务数第二多的人之间即可。

代码

Java

C++

D. Inconvenient Pairs

题解

不难发现，从某个点出发，其不方便的点必然满足下列条件：

1. 如下图红线所示，这个点必然在最近的、两侧的、垂直的路之间。
2. 如下图虚线所示，这个点和出发的点不在同一个路上。

于是显然，我们可以通过二分找到满足条件的点。

这个题的难度在于，要根据不同的条件多次二分，实现起来非常的麻烦。因此，建议通过将所有的二分抽象成1-2个函数，这样实现起来方便一些。

代码

Java

C++