Codeforces Round 1039 (Div. 2) VP記錄

A. Recycling Center

考慮到要讓垃圾袋在正常丟棄的數量盡可能多，所以要在沒有乘2前丟掉盡可能多的垃圾。

按照重量降序排序，如果已經大于 \(c\) 則放在最后丟，否則立馬丟然后讓重量乘 \(2\) 。

此方法的重點在于讓每一次 \(c\) 乘 \(2\) 時都使 coin 總消耗量 -1 ，直到不能 \(0 消耗\) 丟棄垃圾。

AC code

B. Deque Process

考慮每次選擇 \(a_l\) 和 \(a_r\) 。

• 如果 \(a_l\) 和 \(a_r\) 相對于前面并且呈上升趨勢，那么選擇 \(a_l\) 和 \(a_r\) 其中較大的一個之后，下一個選項就一定可以下降。
• 如果 \(a_l\) 和 \(a_r\) 相對于前面并且呈下降趨勢，那么選擇 \(a_l\) 和 \(a_r\) 其中較大的一個之后，下一個選項就一定可以上升
• 如果 \(a_l\) 和 \(a_r\) 相對于前面呈不同趨勢，那么選擇 \(a_l\) 和 \(a_r\) 其中呈相反趨勢的一個之后，下一個選項就一定可以另一個趨勢。

所以只要這么選，序列的上升/下降趨勢一定可以在兩個周期內改變。符合題目

• \(a_i < a_{i+1} < a_{i+2} < a_{i+3} < a_{i+4}\)
• \(a_i > a_{i+1} > a_{i+2} > a_{i+3} > a_{i+4}\)
  的要求。

AC code

C. Leftmost Below

個人認為難度小于B。

假設填入第1個數 \(a_1\) 。
$a_1,0,0,0,0 ... $
然后填入第2個數 \(a_2\) 時先將其分解為 \(a_1-1\) 和 \(a_2-a_1+1\) 。
$a_1,a_1-1,0,0,0 ... $
所以要求 \(a_2-a_1+1 \le a_1\)
$a_1,a_2,0,0,0 ... $
然后取 \(k = min(a_1...a_i)\)
所以要求 \(a_i \le 2k-1\)
如果符合 \(a_i \le 2min(a_1...a_{i-1})-1\) 那么輸出 \(Yes\) 否則輸出 \(No\) 。

AC code

D. Sum of LDS

考慮到題目特殊的性質 $ \max(p_i, p_{i+1}) > p_{i+2} $ 可以證明當 \(p_i > p_i+1\) 時， \(p_i\) 和 \(p_{i+1}\) 一定最長的LDS的一部分。

所以如果 \(p_i < p_i+1\) 那么只有一個點是LDS的一部分，否則只能有1的貢獻。

AC code