A. Ilya and Bank Account
- 模拟。
B. Ilya and Queries
- 前缀和。
C. Ilya and Matrix
- 考虑每个元素的贡献。
- 边长为\(2^n\)时,贡献为最大值;
- 边长为\(2^{n-1}\)时,贡献为前4大值;
- 边长为\(2^{n-2}\)时,贡献为前16大值;
- 以此类推。
D. Ilya and Roads
- \(dp(i,j)\)表示前\(i\)个洞修复了\(j\)个的最小代价。
- \(dp(i,j)=min\{dp(k,j-(i-k))+c\}\),\(c\)是\(r=i\)的所有公司。
- 根据转移式子,很容易想到区间最小值问题,一开始用线段树,然后对公司的\(l_i\)排序,可以利用单调栈优化。