Codeforces Round #738 ABCD 题解 (Java/C++)

A. Mocha and Math

题解

因为$a\&b\leq a$。因此,我们只需要把所有数与一遍即可。

代码

Java

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

C++

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

B. Mocha and Red and Blue

题解

贪心即可。如果一个问号的旁边有字母,那么就填一个不同的。如果出现冲突,那么就随便填一个。

代码

Java

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

C++

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

C. Mocha and Hiking

题解

首先,根据题意,如果不考虑第n+1个村子,那么从1走到n是不会有任何问题的。

接着我们发现,所有1到n的所有村子都有一条边连接到n+1个村子,只是方向不定。于是有三种情况:
1. n+1能通往第1个村子。那么我们就按照n+1, 1, 2, 3...的顺序走即可。
2. 如果第n个村子能通往n+1。那么我们就按照1, 2, 3...n, n+1的顺序走即可。
3. 因为每个村子只能走一次,所以我们一定能找出这样的排列1,2,3,...,i,n+1,i+1,...,n。否则如果存在i,n+1,i+2,则i+1一定不可达。

代码

Java

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

C++

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

D. Mocha and Diana

关键点有两个,一个是边数必为max(n-1-m1,n-1-m2),也就是最终两个森林中的一个会变成一棵树。第二个是,既然会变成一棵树,那不妨从森林中随便选一棵树,把其他的树合并进来。

Codeforces Round #738 Mocha and Diana (hard&easy) 题解 (Java/C++)
题解首先,显而易见,我们会使用并查集来判断两个点是不是在同一个树里。我们可以得到一个结论,最终能添加的边数为$\max(n-1-m1,n-1-m2)$。也就是说:两个森林中至少有一个森林最终会合并成为一棵树。
点击上面链接查看详细题解