Educational Codeforces Round 46

心得

平日練習隨意寫的

A

水題，略

B

水題，略

C. Covered Points Count

AC code

利用掃描線的概念，按照 $x$ 軸順序排序，將事件排好記數即可。

D. Yet Another Problem On a Subsequence

AC code

可以利用動態規劃(DP)來計算答案，若子序列 $p$ 是合法的，則將 $p$ 的第一個 good array 去掉後剩餘的部分也是合法的，假定 $dp[i]$ 表示子序列開頭在第 $i$ 項時，有多少數列滿足題目的條件，若 $a_i\le 0$，則答案為 $0$，否則，可以在第 $i$ 項後的 $j$ 個數字任意挑 $a_i$ 個數字，挑完後在乘上 $d[j+1]$，為剩下的部分有多少合法序列。最後的答案即為 dp 陣列的總和。

$$dp[i]=\{\begin{array}{ll}1& i=N+1\\ \sum _{j=i+a_i}^n(\genfrac{}{}{0ex}{}{j}{i})dp[j+1]& \text{otherwise}\end{array}$$

E. We Need More Bosses

F

G