Codeforces Round #750 ABCDE Solutions (Java/C++)

A. Luntik and Concerts

It's easy to guess the result: just look at the parity of the total time. But the proof of this topic is still a bit interesting.

B. Luntik and Subsequences

Solution:

Just count the number of 0 and 1, denoted as c0 and c1, respectively. The final answer is $c1\cdot 2^{c0}$.

Code:

Java

C++

C. Grandma Capa Knits a Scarf

Solution:

Enumerate the chosen letters by brute force.

Code:

Java

C++

D. Vupsen, Pupsen and 0

Solution:

First of all, it is not difficult to find that we must be able to find a structure such that $|\sum_{i=1}^n(-1)^?\cdot a[i]|\leq 10000$, where the value of ? is based on the method to construct it.
In fact, for any j, $|\sum_{i=1}^j(-1)^?\cdot a[i]|\leq 10000$ can be easily constructed.

We denote $\sum_{i=2}^j(-1)^?\cdot a[i]$ as sum (note that i here starts from 2). So obviously $|sum|\cdot a[1]\pm |a[1]|\cdot sum=0$. So it is obvious that there is such a way to construct:$$b[i]=\begin{cases}
(-1)^?\cdot |sum|,  & \text{if $i=1$} \\[2ex]
(-1)^?\cdot |a[1]|,  & \text{if $i\neq 1$}
\end{cases}
$$The value of ? can be selected according to the situation.

But there are two problems here:

1. The value of sum is 0. In this case, we arbitrarily reverse the sign of any digit.
2. According to the above operation, the maximum value of sum will become 20000. Therefore, the final result needs to be divided by the greatest common divisor of a[1] and sum as the final result.

Code:

Java

C++

E. Pchelyonok and Segments

A DP problem. The key is to find that in fact [l1, r1] is only related to [l2, r2], and further [l2, r2] is only related to [l3, r3], and so on.