20220804NOI模拟赛--考后总结

时间安排

7:30–7:35 读题。
7:35–9:30 T1,期望的 DP 很简单，目测就是一个乱搜的题。考虑枚举每一个质因子，记搜，于是卡常卡到2.8s。过不去。
9:30–10:20 T2,暴力没法写，考虑直接贪心分类讨论。样例很水，而且不好写暴力拍，很自闭。自己手构了几个小数据。
10:20–10:40 T3,猜测每个位置要么是-1要么时K，$n\le 20$可以直接状压。
10:20–12:00 T1,卡常。
12:00–12:30 T3,考虑枚举最优段，然后就不会了，瞎贪。

回顾&反思

T1: 有性质，答案只与指数的最小表示意义下的状态有关，与具体什么底数无关，状态数 $2e5$ 级别，于是暴搜。没发现性质。一个 trick 是，要对一个数所有因数的答案累加可以考虑高位前缀和，拆出所有质因子的底数，钦定前 j-1 个指数不变，那么要么第 j 个也指数也不变继续往后做;要么设当前指数为 $c$ ,加上该位置指数小于等于 $c-1$ ,前 $j-1$ 的和，即该位置指数上界减1,保持前 j-1 不变的子问题。即 $dp[S][j]=dp[S][j+1]+\sum _{K<S}dp[K][j]+W$ ，其中 $S,K$ 表示状态， $K$ 是由 $S$ 延伸出的子状态， $W$ 是单点权值 。
T2: 分类讨论少考虑了一种情况，然后…然后就是大力分类讨论，没错就是一本正经的分类讨论。
T3: 基本思路时枚举最优区间，然后对错误算法的答案 DP，在此基础上优化。具体还不会。