11.5 dmy NOIP模拟赛DAY4 总结

时间安排

• $7:40-8:00$ 开题。把题目都看了一遍。 $T1$ 看起来不难。 $T2$ 是构造，而且有股 $NOIP2023T2$ 的味，感觉想起来会很晕。 $T3$ 看起来是正常的计数。 $T4$ 字符串，一眼感觉根之前 jsy 说过的一道题有点想，但是我不会求矩阵的逆！！！所以感觉这题也可以 $hash$ 做啥的。
• $8:00-8:45$ 写 $T1$，发现暴力 $dp$ 式子是简单的。然后 $d{p}_i$ 是从 $d{p}_{i\%j}$ 转移过来，看起来很像把 $\%$ 给拆成 $i-\lfloor \frac{i}{j}\rfloor \times j$，然后就可以数论分块。但是 这个式子怎么在下标里？？没法拆开感觉做不了？？想了一会儿发现这个东西相当于在 $dp$ 数组上以 $\lfloor \frac{i}{j}\rfloor$ 为步长往前跳。然后可以对这个步长根号分治。这样复杂度 $O(n\times \sqrt{n})$。感觉没问题就写了一发。一测大样例，卧槽怎么 $T$ 了？？？后来调 $10min$ 发现自己转移写错导致复杂度假了。然后改改就过了。和暴力的答案数组对了一下，没什么问题，就跳了。
• $8:45-9:20$ 尝试做 $T2$，发现会做 $30pts$。然后去推性质感觉有点乱。想着等会儿再回来看看。
• $9:20-10:00$ 想 $T3$。发现 $n\le 10$ 可以直接把子序列全部搜出来然后 $dp$。 $k=2$ 就相当于求有多少本质不同的子序列。 $k=3$ 相当于求所有本质不同的子序列的本质不同子序列的数量。感觉这个有点抽象，但是还是可以冲一冲的。就开始想。中间想过一些做法，但是总感觉有点假。 $9:50$ 了还没有什么很明确的做法，有点急，就把前两档写了。
• $10:15-10:40$ 先写了一个 $k=3$ 的做法，发现过不了大样例。有一点难受。但是很快想到了比较抽象的 $dp$，而且看起来挺对的，就写了。写完后发现能过大样例，感觉很开心。这样 $T3$ 就有 $45pts$ 了。
• $10:40-11:50$ 思考再三，决定还是先开 $T2$。回去推出了可以对于每条限制连两次边，这样不合法的情况就变成了只需要判断有没有环。如果没有环，从小到大填数就可以了。感觉挺对的，就去写了。先写的暴力，感觉很顺。交上去过了部分分的数据。然后去写正解，发现交上去过了大样例？？！不知道大样例水不水，但还是挺开心的。
• $11:50-12:00$ 看 $T4$， 发现 $10pts$ 很简单。 $n\le 3000$ 应该不难但是应该挺难写。发现不会别的分，就写了 $n^3$ 暴力。中间尝试用 $n^3$ 去跑 $3000$，然后 $T$ 飞了，就觉得肯定做不了。交上去吃饭了。

成绩

100 + 100 + 45 + 10 = 255
rk16
没挂

反思

• 暴力写的还是有点晚，应该会暴力后如果能快速写完还是尽量早点写，防止最后暴力写不完。
• 赛后发现很多人 $n^3$ 草过了 $3000$，发现我的代码只要不用 STL 就也能过了，有点难泵。