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

A. Eshag Loves Big Arrays

题解

既然可以选择任意子序列。那么只要某个数x,高于了数组的最小值。那么迟早这个x会和某个最小值相邻,并且被删掉。所以统计高于最小值的值的数目就好。

代码

Java

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

C++

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

B. Sifid and Strange Subsequences

题解

首先,选择所有小于等于0的数一定是个可能的选项。

接着,考虑要选择正数的情况。我们可以立刻发现,最多只能选择一个正数。既然只能选择一个正数,那么显然会选择尽可能小的那一个正数。
剩下的问题就很好办了,对于剩下的小于等于0的数,从大到小依次选择就好了。过程中保证相邻两个数的差的绝对值大于等于哪个正数。

最后,记得在全部选小于等于0的数和选一个正数的结果之间取一个最大值。

代码

Java

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

C++

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

C. Parsa's Humongous Tree

典型的树上DP。

Codeforces Round #722 Parsa’s Humongous Tree 题解 (Java/C++)
题解首先第一个结论是:对于任意一个顶点,要么选择l,要么选择r。因为选择某个l和r之间的值的情况只有一种:就是样例2中的那种。但是其实对于样例2,仍然可以选择l和r中的一个。
点击上面链接查看详细题解

D. Kavi on Pairing Duty

其实把n=4自己仔细的画出来就好了。可以说70%的递推关系比较明显。唯一藏得比较深的是n=4的时候,可以通过重复两次n=2来得到一个不同的解。

Codeforces Round #722 Kavi on Pairing Duty 题解 (Java/C++)
题解令dp[i]表示n=i时的答案。我们以n=4为例说明解法。首先考虑两种特殊情况,如下图所示:
点击上面链接查看详细题解