• 这是关于NOIp2021VP的总结和改题记录

可惜VP之前忘了周日提前回宿舍，所以没有打足时，少打了50min左右。

但是得分也想必不会有很大波动——最多再多出T4的不到30分暴力。

最终得分情况是 100 + 10 + 32 + 0 = 142 ，在去年可以擦线省一，但是对于难以有更高的奢望。

这分数是不令人满意的，所以我应当从中汲取经验。

赛时出现了几个失误 ：

  • 对数组空间预估错误。

T1开场想到筛法，然后觉得 $1e7$ 数组开不下转而乱搞。虽然最终也能过题，但是乱搞过题是不应当的，而且浪费了大量时间进行卡常，并具有不正确的复杂度。

后来经交流发现数组开的下，于是先想了线性筛。发现不会写之后转为埃氏筛，但是总时间花费很短。

  • T2暴力没有优化到最优，且没有想到状压DP正解。

想不出正解是能力问题，应当多做DP题加以训练。

暴力则是因为没有优化掉一个显然可以优化掉的 $n$ 导致少了 $10$ 分。这是不应当的。

  • T3没有观察出关键性质，最终只靠乱搞骗到 $32$ 分，然而看出性质的乱搞可以过题。

关键性质是由单调递增看出操作的本质是差分数组上进行交换。

在此性质的基础上，我们可以由方差的意义——刻画数据的离散程度——来得到我们得到的差分数组应当是一个单谷函数。

于是可以随机化来维护这个单谷函数，在恰当的随机策略下可以通过本题。

这些性质对于我来说并不是显然的。

虽然赛时着重注意了数列的单调性，但仍没有发现交换差分的性质，或许发现之后也不能想到维护单谷函数而难以得到关键。

我的洞察力不够，观察力与发现性质的能力不够。

今后做题时应当着重注意是否可以由已知条件得到关键性质，且应当更多方面的考虑尚未使用的条件。

以及把手玩样例等过程更多的做到“可视化”，就能更容易地发现一些性质（罢）。

下面是师父的教训 ：

  • 观察敏锐吗

  • 有没有积极尝试换一个模型去分析

  • 有没有办法判断正解大概是什么，和什么有关

  • 有没有办法判断自己的思路是不是有戏的

  • 能否判断在考试结束之前，自己使用哪种写法能够最大化基础分数

这些东西是最基础的,但是如果在这些方面欠缺，那么解题能力便是低下的.

而这些，一言以蔽之，即为经验。