Codeforces Round #738 ABCD Solutions (Java/C++)

A. Mocha and Math

Solution:

Because $a\&b\leq a$. So, the answer is $a_1\&a_2\&a_3\&...\&a_n$.

Code:

Java

C++

B. Mocha and Red and Blue

Solution:

Just be greedy. If there is a letter next to a question mark, then fill the question mark in a different one. If there is a conflict, just fill in any one of color.

Code:

Java

C++

C. Mocha and Hiking

Solution:

First of all, according to the problem description, if the n+1th village is not considered, there will be no problem going from 1 to n.

Then we found that all villages from 1 to n have an edge connected to n+1 village, but the direction is uncertain. So there are three situations:
1. n+1 can lead to the first village. Then we just follow the order of n+1, 1, 2, 3...
2. If the nth village can lead to n+1. Then we just follow the order of 1, 2, 3...n, n+1.
3. Because each village can only go once, we must be able to find such an arrangement like 1, 2, 3,...,i,n+1,i+1,...,n. Otherwise, if i, n+1, i+2 exist, i+1 must be unreachable.

Code:

Java

C++

D. Mocha and Diana

There are two key point of this problem.
One is the number of edges must be max(n-1-m1,n-1-m2). So that one of two forest will be merged to one tree.
Second one is, since it will become a tree, we can choose any one of the tree in the forest and merge other trees to it.