CSP-S 2022 简单分析

本文是由今天写的分析 slide 直接搬运过来的。

题目情况

逐题看

• 第 1 题：

  • 签到题。

  • 有图不连通的坑。

  • 需要（用 meet in the middle 的）选手认识到需要维护最大、次大、第三大 这 3 项才可以保证转移不漏且正确。

  • 或许可以警示我们不要盲目自信，该用草稿纸的时候就用草稿纸。

• 第 2 题：

  • 签到题。

  • 分类讨论一下各种情况，并写一个合适的数据结构，能讨论完备并写对即可。

• 第 3 题：

  • 带一个诈骗的智慧题。

  • 首先，当一张有向图满足 所有点出度均为 $1$（条件 1）时，其必然构成一个基环内向树森林，从而已经满足 所有点都可以到达一个大小大于 $1$ 的 SCC（条件 2）。所以，只需要判断条件 1 是否满足即可。

  • 如何维护当前是否所有点出度均为 $1$ 呢？

  • 如果将每个点的出度情况排成一个序列，处理序列是否和一个固定序列相同，就可以序列哈希了。

  • 据说可以参考 CF1746F 这道题的想法。

• 第 4 题：

  • 其实算是中规中矩的 DDP 题。

  • 当 $k = 1, 2$ 时，易见直接在 $u \to v$ 的路径上选点是优的；$k = 3$ 时可以绕出去一次，并且这个绕出去绕到的点到 $u \to v$ 路径距离为 $1$。

  • 树上路径上 DP，考虑 DDP。

总体看

• 四道题中有三道题以图论为载体，其中第 3 题对两个约束条件的关系（条件 1 是条件 2 的充分不必要条件）的观察考察了图论素养和理解力，另外两道题则与图论本身关系不大。

• 前两题都需要细致的分类讨论。

• 后两题都需要观察出一些事实并基于此解答。

• 第 3 题可能需要题目积累或灵机一动，另三道题实际上不是十分难想到。

• 比较需要代码能力和速度。

• 洛谷上目前给四道题的评级是：蓝、绿、紫、紫，我个人觉得是合理的。

个人情况

得分

• 洛谷上的民间数据测评结果：$\rm{\color{red}35\color{black}+\color{green}100\color{black}+\color{red}25\color{black}+\color{orange}40\color{black}=\color{orange}200\ \color{black}pts}$；

• InfOJ 上的民间数据测评结果：$\rm{\color{red}30\color{black}+\color{green}100\color{black}+\color{orange}40\color{black}+\color{orange}40\color{black}=\color{orange}210\ \color{black}pts}$。

逐题分析

• 第 1 题：

  • 开场约 20min 想到做法，约 40min 过了样例。

  • 很自信，没有对拍。

  • 没有仔细思考，也没有草稿纸上具体分析，也因为没有对拍而没有面向数据发现问题的机会。

  • 一个状态有两个属性，所以要正确转移，应当维护一个状态的最大、次大、第三大的转移来源。

  • 我直接套用了一个状态只有一个属性时维护最大和次大转移来源的做法。看来是对其理解不够。

  • 我甚至进行了一通没有在草稿纸上的假证明，以为连次大到次大这种转移都是不必要的。

  • 教训是： 不要盲目自信；该用草稿纸的时候就用草稿纸；对一些想到的经典做法要仔细考察其适用情况，要理解到位。

• 第 2 题：

  • 这道题顺利过了，本身没有什么问题。

  • 写 ST 表和写线段树我觉得代码难度可能区别并不是很大，不过如果选择了封装可能实现起来就容易一些。

  • 我写的是不封装的线段树，一共实现了 blda bldb qpxa qpna qnxa qnna qmxb qmnb 这 8 个函数。

  • 码了大概一个小时。本题一共用时大概 80 分钟。

  • 这道题处理得慢了点，所以后面比较局促。

• 第 3 题：

  • 这道题别说让我看出条件 1 和条件 2 的关系了，我直接一开始就很谔谔地把条件 2 读错了。

  • 第 1 个样例都没有通过，我看了看样例解释的图，才明白正确的题意是什么。

  • 彼时时间已很紧了，所以快速地加了点正确性都不对的修改就放下了。

  • 时间紧迫时的读题能力（也就包括了不浪费时间在读错题上的能力）需要加强。至于序列哈希的做法，那大概是需要平时做题积攒经验。

• 第 4 题：

  • 这道题和第 3 题一样是在时间比较紧迫的情况下看的。

  • 第 3 题体现了需要时间紧迫时的读准题的能力，这道题体现了需要时间紧迫时的想清楚题的能力。

  • 这道题容易看出 DDP 这个方向，关键在于要把 DP 转移想清楚了。

  • 我以为 $k = 3$ 时绕出去也是没用的，成功地让我的暴力分也不可能拿满。

  • 码力也不够，看了剩下的时间，不敢写 DDP。

总体认识

• 想题一要想准二要想快，码题一要码准二要码快。

• 平时训练要积攒一些方法技巧，要把一个解决问题的方法理解到位。

以下内容仅供参考。

几个省的情况

陕西省信息来自某校选测，其余三省信息来自 InfOJ 的民间数据和模拟测评。

陕西（SN），湖南（HN），北京（BJ），重庆（CQ）。

陕西省（SN）

• $\ge 300$：$4 \sim 5$ 人；

• $\ge 250$：$7$ 人。

事实证明，拿稳应该拿的分是很重要的。

湖南省（HN）

• 非零分提交：$458$ 人；

• $= 400$：$3$ 人；

• $\ge 300$：$33$ 人；

• $\ge 250$：$54$ 人；

• $\ge 200$：$97$ 人。

第 1 题和第 2 题情况基本相仿，大概 100 人左右拿到了满分。

高分段第 4 题比第 3 题表现好一点，看来 HN 确实更强于稳扎稳打。

北京市（BJ）

• 非零分提交：$701$ 人；

• $= 400$：$6$ 人；

• $\ge 300$：$30$ 人；

• $\ge 250$：$67$ 人；

• $\ge 200$：$126$ 人。

第 1 题和第 2 题情况基本相仿，大概 100 人左右拿到了满分。

高分段第 4 题比第 3 题表现明显好一些，看来 BJ 同样更强于稳扎稳打。

重庆市（CQ）

• 非零分提交：$438$ 人；

• $= 400$：$4$ 人；

• $\ge 300$：$47$ 人；

• $\ge 250$：$87$ 人；

• $\ge 200$：$140$ 人。

第 2 题比第 1 题表现好。

高分段第 4 题比第 3 题明显表现好一些，看来 CQ 同样更强于稳扎稳打。

上面的若干分数段 CQ 基本上都比 HN 和 BJ 表现好，原因之一应该是 CQ 的第 2 题有约 160 人拿到了满分。

结束

各位 NOIP 加油。