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:
- The value of sum is 0. In this case, we arbitrarily reverse the sign of any digit.
- 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.
