Codeforces Round 251 Div.2

Posted on By 二价氢

#A. Devu, the Singer and Churu, the Joker

(略)

#B. Devu, the Dumb Guy

(略),至于为什么是对的我想不需要证明……

#C. Devu and Partitioning of the Array

(稍后补)

#D. Devu and his Brother

将数组$a$升序排序,将$b$降序排序

答案就是\(\sum b_i-a_i\)(\(b_i>a_i\))

为什么是对的?

设$a$数组最小的一项不小于\(x\),\(b\)数组最大的一项不大于\(x\)

显然,对于每一组\((a_i,b_i)\)满足\(a_i<b_i\),对答案的贡献为\((x-a_i)+(b_i-x)\)

后面就不言而喻了……

#E. Devu and Birthday Celebration

首先,用插板法求出\(n\)划分\(f\)份有序的方案数\(\left(\begin{array}{c}n-1\\\\f-1\end{array}\right)\)

然后,用容斥原理加DP即可