Codeforces Round #745 (Div. 2) ABCDE Solutions (Java/C++)

A. CQXYM Count Permutations

Solution:

It is not difficult to think that there are x of i satisfying the condition in an permutations , then if we reverse the permutations, there are 2n-x of i satisfying the condition. For example, [3,2,1,4]=1, then [4,1,2,3]=4-1=3.

Therefore, the number of i that meet the conditions is actually evenly distributed. So the answer is $\frac {2n!} 2$.

Code:

Java

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

C++

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

B. Diameter of Graph

Solution:

Obviously, if m is less than n-1, not all points can be connected, and it must be NO. Similarly, if m is more than $\frac {n \cdot (n-1)} 2$, there must be a duplicate edge, which is also NO.

Obviously, if $k-1\leq 0$, which is the maximum allowable diameter $\leq -1$, it must be NO.
If $k-1=1$, that is, the diameter must be 0, YES if and only if n=1, otherwise NO.
But if $k-1\geq 3$, which is the diameter $\geq 2$, there must be a solution. We can give the structure of the following figure:

In the end, we only have $k-1=2$ left without consideration, that is, the diameter is 0 or 1.
For a diameter of 0, which has just been considered, n must be 1.
If the diameter is 1, there must be an edge between any two points, so YES if and only if $m=\frac {n \cdot (n-1)} 2$, otherwise NO.

Code:

Java

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

C++

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

C. Portal

The key to this question is to find that the final answer must be less than or equal to 16. Then brute force search based on this conclusion.

Codeforces Round #745 (Div. 2) Portal Solution (Java/C++)
Solution:It is not difficult to find that when a=5 and b=4, only 16 steps are required even in the worst case.
Click the link above for detail solution

D. Mathematics Curriculum

The key to this question is: thinking of the maximum value of the interval as the boundary, the interval on the left and right of it does not affect each other at all. So can split sub-question based on this conclusion, and further DP is a natural choice.

Codeforces Round #745 (Div. 2) Mathematics Curriculum Solution (Java/C++)
Solution:First of all, we do not consider the condition that the number of good numbers is exactly equal to k, we first consider the characteristics of the good number itself.
Click the link above for detail solution

E. Train Maintenance

The key to this problem is that the cases where the value of x[i]+x[y] is large and small can be handled separately. And believe that Codeforce can process 100 million calculations in a second.

Codeforces Round #745 (Div. 2) Train Maintenance Solution (Java/C++)
Solution:First of all, we can almost immediately notice that if x[i]>m, then this must have no effect, and we can ignore it directly. Therefore, the value range of x[i] is reduced from 0~$10^9$ to 0~$2\cdot 10^5$.
Click the link above for detail solution