23.12.9考试总结

分数 : $60$ （$50+10+0+0$)

A. stick

---

先是一个数字，然后一串$0$，最后一串$8$。贪就完了。

注意模数是 $998244$8$53$。挂分 $50pts$

B. game

---

正解爆搜。少打 break挂 $90pts$。

答案很多，所以 $yes$ 跑得很快。

最坏情况$5\times 6$，此时$O(1^4\times2^{14}\times3^{16})$。

注意到数据很小，考虑可行性剪枝即可。

来自 永远的7日之都 .

C. noip

---

万恶的 $O2$，$RE\ \ 0$。

字典序从大到小搜索,$DP$ 预处理 $每个后缀首字母确定的情况下所能得到的最大权值$ ，判断当前是否 $\geq\ x$ $(可行性剪枝)$。

学的是 $DP作为部分$ 的思路。

D. remove

---

区间 $DP$。求

$$min \left\{ \begin{aligned} a \times k + b\times\sum\limits_{i=1}^{k} \Big (max_i-min_i\Big) \end{aligned} \right\}$$

设方程 $f_{l,r,max,min}$ 表示 消除区间 $[l,r]$ 使其剩下的最大值为 max ，最小值为 min 的最小代价。$g_{l,r}$ 表示 区间$[l,r]$中全消的最小代价。

所以

1. 初始化 :

$g_{l,r}=min${$f_{l,r,max,min}+a+b\times (r-l)^2$}

2. 转移

左边空或右边空 :

• $f_{l,r,max,min}=\min\{g_{l,k} + f_{k+1,r,max,min}\}$
• $f_{l,r,max,min}=\min\{g_{k+1,r} + f_{l,k,max,min}\}$

两边都空

• $f_{l,r,max,min}=\min\{f_{l,r,max,min} + f_{k+1,r,max,min}\}$

端点刷表

• $f_{l,r+1,max(max,w_l),min(min,w_r)}=f_{l,r,max,min}$

3. g?

   $g_{l,r}=min${$f_{l,r,max,min}+a+b\times(max-min)^2$}

4. 离散化后 $O(n^4)$

---

问题：

1. 手抄斩手，使用CV大发。

2. O2 要看返回值。

3. 对拍数据要把时间卡到满，不能放水。