稳健型选手。
1kri
·
·
个人记录
根据省选用官方数据测出的民间榜来分析如何在 \text{NOI} 中拿金牌。
默认读者是全国前 150 名水平。
今年的统一省选，题型接近传统 \text{NOI}，样例也接近 \text{NOI} 放样例的风格，是有区分度的好比赛。就假设这场作为 \text{NOI}，来看看如何拿到金牌。
正文参考资料
根据这份资料，我们可以发现正式选手（假设前 50 名全部进入 \text{A} 队）的集训队分数线是 357 分。考虑误差，我们认为算上笔试和 \text{A} 类加分的集训队分数线是 460 分。
我们来分析一下每道题目的通过人数，发现除了最后一题外其余每题都有不少人通过。
而如果在每题中都能拿到全国第 20 名的分数是什么水平呢？国家队长水平！
这说明大家每天的得分是有侧重性的，即使是国家队都很难在比赛时间内做到把所有分数拿满。
来分析一下每道题目有多少分数是“高档大众分”：
这些分数加在一起是 353 分，如果进了 \text{A} 队且笔试没挂分总分就是 458 分，很接近队线。
我们先来看下拿到所有的“高档大众分”需要哪些能力。
$\text{D1T2}$ 的大众分需要找到一些基本的性质，并要求一定的代码实现能力。
$\text{D2T1}$，$\text{D2T2}$ 的大众分需要较高的代码实现能力，尤其是 $\text{D2T1}$。
我们发现，“高档大众分”主要侧重点是代码实现而非思维，这也就是我认为的“稳健型选手”应该侧重的地方。
我来说下自己对于稳健型选手的定义：无论遇到什么风格的题目，都能取得不错的成绩，至少不会被拉开较大差距。
思维上是有侧重点的，有的选手喜欢计数，有的选手喜欢贪心。而代码能力有更多的共通性，能写出复杂 $\text{dp}$ 的选手复杂贪心也照样能写对。
思维其实是不如代码能力稳定的。很多题目在不自知的情况下第一步转换复杂了，就可能永远也想不出来。思考题目的过程并不总是循序渐进的，有时需要突然来的灵感，但这灵感什么时候能来，或者能不能来，都是无法确定的。而代码能力除了极少数时候外，大多数情况下都是稳定的。
所以我认为，想要冲击金牌的选手可能更需要侧重培养自己的代码能力。
现在假设我们拿到了“高档大众分”，还需要在什么地方取得突破呢？
我们发现，$\text{D1T3}$ 的 $\text{C}$ 性质是剩下的分数中最好拿到的。它无需很多思考，对于代码能力的考察也是套路数据结构，很容易写对。但是因为它要写一个线段数分治和一个树剖线段树，耗时间，所以场上鲜有选手单独写这档分。
但是我认为，在时间充裕的情况下，花半个小时拿到 $6$ 分其实是很值得的。事后来看，这 $6$ 分也许就是决定金牌的关键点。
像这样的部分分，我称其为“稳定的低性价比”部分分。在最后一个小时里，如果不能取得突破，就应该去尝试拿到这种分数。
我们应该如何获得更高的分数来稳住集训队。
我们发现，其实第一天的高档暴力分很可以在 $\text{2h}$ 内写完，剩下的时间有对拍和想题两种决策。
发现 $\text{D1T2}$ 我们已经写过暴力了，所以不花什么时间就能挂个拍。$\text{D1T3}$ 样例看上去很强，无需对拍。$\text{D1T1}$ 代码简单，暴力不好写，自己检查就行。
那么，我们还有约 $\text{2.5h}$ 的时间去想题。这么长时间的思考，很容易想出 $\text{D1T2}$ 的多项式复杂度暴力，再加点优化做到 $O(n^{2.5})$，就能拿到 $75$ 分。
最后时间发现难以突破，就拼一个 $\text{D1T3}$ 的 $\text{C}$ 性质，$6$ 分。
这就是我的得分分布：$100+75+54$。虽然不高，但它很稳健。
如果你精通数据结构，在 $\text{2.5h}$ 内是有希望将 $\text{D1T3}$ 切掉的。
这样的得分分布是：$100+55+100$。
后者对于第二天的优势会很大，只要不连续犯错误应该是稳了。
我们来看下前者在第二天应该如何决策。
$\text{D2T1}$ 是在 $\text{Day1}$ 发挥并不特别突出选手的决胜题，如果能短时间内想出写对，就有集训队。而没想出来，没写对，或者花费时间过长，就很难进队了，当然也并非完全无可能。
这种题目思维和实现上都考察选手的细节。它没有很难想的地方，只要循序渐进的深入思考就行。代码实现上，就很考验选手的基本功了。
假设我们花了 $\text{2h}$ 解决了这道题目。
发现第三题非常不可做，读完题后花很少时间写了 $10$ 分暴力，大概还是剩了 $\text{2.5h}$。
第一题难以对拍，就把时间全部用来做第二题。
即使第一步建图的转换没看出来，也能稳扎稳打写出 $40$ 分暴力，就擦线进集了。
如果看出来了树和基还树的转换，应该怎么做？
我考场上是写了两个 $\text{namespace}$ 处理两种情况，每个 $\text{namespace}$ 初始时都是暴力，然后用正确的代码来替代其中的内容。
这样是很正确的。因为我们已经有了暴力分，且最后即使只写对了基环树，也能拿到很多特殊性质分。这里需要注意，我们在写之前看一下数据范围，只基环树有很多分，但只树就不行，所以我们应该先写基环树。
这样，只要看出转换，稳健型选手就能拿到很多暴力分，也就稳集了。
发现我们刚才所有的讨论都是建立在知道高档大众分的情况下。而在考场上，其实是不知道其他选手发挥的。我认为在这种情况下，应该以自己 $\text{10min}$ 内想出或有明确思路的部分分作为高档大众分，这就需要我们平时锻炼快速思考的能力。
愿大家都能成为稳健型选手！
