预期	实际	\(\Delta\)
A	100	100	0
B	100	100	0
C	100	0	-100
D	10	29	+29
E	50	100	+50
总计	360	329	-31

A Largest Rectangle in a Histogram

单调栈板子

B 没有上司的舞会

树形\(DP\)，\(f_{u,0}\)表示以\(u\)为根的子树在不选\(u\)时最大快乐指数，\(f_{u,1}\)为选\(u\)的最大快乐指数，转移：

\[\begin{aligned} f_{u,0}=\sum \max(f_{v,0},f_{v,1})\\ f_{u,1}=\sum f_{v,0} \end{aligned} \]

C 阶乘分解

题目：将\(n!\)分解为\(\prod p_i^{c_i}\)，输出\(p_i\)和\(c_i\)

可以\(O(n)\)筛出\(n\)以内的所有质数，那么问题在于\(c_i\)如何求

在1~n中一共有\(\lfloor \frac{n}{p_i} \rfloor\)个数是\(p_i\)的倍数（分解后至少有一个\(p_i\)），在其中又有\(\lfloor \frac{n}{p_i^2} \rfloor\)个数至少含另一个\(p_i\)，以此类推

所以\(c_i=\displaystyle\sum_{p_i^k\leq n} \lfloor \frac{n}{p_i^k}\rfloor\)

D 欧拉回路

没有SP的欧拉回路就是耍流氓

E 括号配对

题目：输入一个括号序列，求至少添加几个括号能使括号匹配

灵感来源：\(CQOI2007\ \ paint\)

第一想法肯定是想贪心的，但是贪不动，显然也不可能搜，不太会剪枝

然后想\(DP\)，从而联想到上面的题

设\(f_{l,r}\)表示将\([l,r]\)的括号匹配掉需要加几个括号，那么有

\[f_{l,r}= \begin{cases} f_{l+1,r-1}\ \ s_l \ \ match \ \ s_r\\ \min(f_{l,k}+f_{k+1,r}) \end{cases} \]