[总结] 2024 CSP-S 模拟赛 Day3

· · 学习·文化课

2024 CSP-S 模拟赛 Day3

前言

主要想反思一下 \text{T2} 的问题。

T2

考试的时候大概一个小时左右会了一个 O(nk)，后面写完 \text{T4} 的暴力，又花半个小时看了一下 \text{T3}，留了大概 50 \min 去写这个 O(nk) 的暴力，最后样例全 0 没时间调试，然后 \text{0pts}，本来期望有 \text{60pts} 的。

赛后发现和我同一复杂度的不同做法直接过了（甚至 O(n^2k) 也过了），数据好水。。。

其实这个题二分和堆的两种想法正常人都能想到，只是因为 k 比较小（以前遇到的题如果是二分 k 一般比较大）所以我偏向堆去思考。

但是像这样 O(方案数) 的去 \text{check}，以后应该还会碰到，保证搜出来的每个方案都是合法的即可。

关于为什么没有想出正解，因为我用堆的思路一开始是存储整个序列哪些元素被选了，为了去重钦定了移动了 x 之后下次移动必须要移动编号小于 x 的 1。

这样的话整体思路和去重思路都没有问题，就是状态复杂度太高了，其实简化一下状态，只需要记录当前操作的是哪一个 1 和前驱后继的位置就可以了，O(nk) 就变成了 O(k)。

然而我赛时想的是状态复杂度过高并不影响时间，主要是导致空间太大了，然后就想去把优先队列的扩展过程改成一个 \text{dfs} 的实现，发现更不好做，就浪费了很多时间。

这种情况的话还是要想办法去简化状态，考虑哪些信息是真正有用的，哪些又是可以省略的，可能对 \text{DP} 也会有帮助。

策略问题

我一直以来都是到考试最后统一留 1 个小时的时间去写所有没做出来的题的部分分，但是我发现这显然不太够，尤其是在没过题，心比较慌的情况下。

以后打算考试时间过半的时候，如果 \text{T2} 还没有出正解思路的话就先写掉后面两道题的部分分，然后再回来全力看 \text{T2}。这样可以避免在后期三道题反复横跳的情况。