Codeforces Round #722 (Div. 2) ABCD Solutions (Java/C++)

A. Eshag Loves Big Arrays

Solution:

Because can choose any subsequence. So, for some number x which is bigger than the minimum number of the array. This x will be nearby one of minimum number earlier or later. And this x will be removed then.

Code:

Java

C++

B. Sifid and Strange Subsequences

题解

First, choose all numbers which is less or equal than 0 is a choice.

Then we consider if we choose some positive numbers.
We can find that: at most we can pick up one positive number. And so, of course, it is better to choose smaller number. So, we choose the minimum positive value.
So, for the remained numbers, we choose the number from big to small one by one. And just need make sure the absolute value of the difference between two adjacent numbers is more or equal to the positive number.

Finally, we choose the max value between "all number less/equal to 0" and "one positive number".

代码

Java

C++

C. Parsa's Humongous Tree

Very classical problem of DP on the tree.

Codeforces Round #722 Parsa’s Humongous Tree Solution (Java/C++)

Solution:The first conclusion is: for any vertex, it will choose l or r. Because if and only if the case like example 2 can choose value between l and r

xloypaypa's Blogxloypaypa

Click the link above for more details

D. Kavi on Pairing Duty

Just solve the case which n=4 manually. 70% of cases is obviously. The only hidden case is when n=4, can get another solution which is repeat the n=2 twice.