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

A. Eshag Loves Big Arrays

题解

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

代码

Java

C++

B. Sifid and Strange Subsequences

题解

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

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

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

代码

Java

C++

C. Parsa's Humongous Tree

典型的树上DP。

D. Kavi on Pairing Duty

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