Codeforces Round #750 ABCDE 题解 (Java/C++)

A. Luntik and Concerts

很容易可以猜到结果：就是看总时间的奇偶性。但是这个题目的证明还是有点意思的。

Codeforces Round #750 Luntik and Concerts 题解 (Java/C++)

题解先说结论，结论是，如果总时间数是偶数则输出0，否则输出1。首先我们考虑只有3分钟的歌的情况。这种情况的答案显然是0或者3。

xloypaypa的博客xloypaypa

点击上面链接查看详细题解

B. Luntik and Subsequences

题解

统计0和1的数目即可，分别记为c0和c1。最终的答案就是$c1\cdot 2^{c0}$。

代码

Java

C++

C. Grandma Capa Knits a Scarf

题解

暴力枚举选择的字母即可。

代码

Java

C++

D. Vupsen, Pupsen and 0

题解

首先，不难发现，我们一定可以找到一种构造使得$|\sum_{i=1}^n(-1)^?\cdot a[i]|\leq 10000$，其中?的取值根据构造方法而定。
事实上对于任意的j，$|\sum_{i=1}^j(-1)^?\cdot a[i]|\leq 10000$都可以轻易的构造出来。

我们记$\sum_{i=2}^j(-1)^?\cdot a[i]$为sum（注意，这里的i是从2开始的）。于是很明显的$|sum|\cdot a[1]\pm |a[1]|\cdot sum=0$。因此很明显有这样的构造：$$b[i]=\begin{cases}
(-1)^?\cdot |sum|, & \text{if $i=1$} \\[2ex]
(-1)^?\cdot |a[1]|, & \text{if $i\neq 1$}
\end{cases}
$$其中?的值按情况选取即可。

但这里有两个问题：

sum的值为0。这种情况下，我们任意逆转任意一位的正负号即可。
根据上面的操作，会导致sum的最大值变为20000。所以最终的结果需要给a[1]和sum除以其最大公约数后再作为最终结果。

代码

Java

C++

E. Pchelyonok and Segments

一个比较明显的DP。关键是发现其实[l1, r1]只和[l2, r2]有关，进一步[l2, r2]只和[l3, r3]有关，以此类推。