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

A. Mocha and Math

题解

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

代码

Java

C++

B. Mocha and Red and Blue

题解

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

代码

Java

C++

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

C++

D. Mocha and Diana

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