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

A. Luntik and Concerts

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

Codeforces Round #750 Luntik and Concerts 题解 (Java/C++)
题解先说结论,结论是,如果总时间数是偶数则输出0,否则输出1。首先我们考虑只有3分钟的歌的情况。这种情况的答案显然是0或者3。
点击上面链接查看详细题解

B. Luntik and Subsequences

题解

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

代码

Java

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

C++

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

C. Grandma Capa Knits a Scarf

题解

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

代码

Java

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

C++

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

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}
$$其中?的值按情况选取即可。

但这里有两个问题:

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

代码

Java

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

C++

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

E. Pchelyonok and Segments

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

Codeforces Round #750 Pchelyonok and Segments 题解 (Java/C++)
题解我们以k=3,n=10为例,考虑[l1, r1]的选择,考虑下面两种选择:[4, 6]和[3, 5]。 我们先考虑[4, 6]的可行性。根据题目定义,[4, 6]需要找到一个k=2的情况,使得sum(4, 6)<sum(l2,r2)
点击上面链接查看详细题解