历年 CSP-J 第二轮算法题型分析与总结

零、背景

CSP-J/S 是从 2019 年开始举办的。

截止目前，我已经完成了 2019 年以来所有 CSP-J 第二轮编程算法题，并输出了题解。

今天打算统计一下 2019 年到 2024 年近 6 年 CSP-J 编程算法的难度、题型，从而总结出常见的题型。

代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/other/CSP-J/

一、题解

历年题解及题目整理在下表，点击第一列可查看具体比赛的题解。

二、难度

CSP-J/S 的难度依次是入门、普及−、普及/提高−、普及+/提高、提高+/省选−、省选/NOI−、NOI/NOI+/CTSC。

对于 CSP-J，每年有四道题，难度一般分布在入门、普及−、普及/提高−、普及+/提高这四个初级难度。

如下图，是历年来四道题的难度。

除了 2022 年四道题分别对应四个不同难度外，其他年份通常会有一道题难度提升。

2019 年，没有普及/提高−，提高一个难度为 普及+/提高。
2020 年，没有普及/提高−，提高一个难度为 普及+/提高。 2021 年，没有入门，提升两个难度为 普及/提高−。
2023 年，没有入门，提升一个难度为普及−。
2024 年，没有普及+/提高，提升一个难度为 提高+/省选−。

2022 年没有提升难度，并不代表当年题目较为简单。例如第三题是模拟语法树，对于大部分人来说仍然相当有难度。

总体来看，难度主要集中在三个级别：普及−占比 29.1%、普及/提高−占比 20.8%、普及+/提高占比 29.1%。
入门占比 16.67%，比例也不低。

三、题型

看 CSP-J 历年来的题型，涉及基础送分题、二分、线段树、贪心、模拟、动态规划、最短路等题型。

可以发现，基础题算是必出，快速幂也算基础题就是占比 100%。
出题概率大于 50% 的有：二分 66.7%，线段树 50%，模拟 83.3%，动态规划 66.7%。
出题较高的有 贪心 33.3%，语法树 33.3%，最短路 33.3%。

四、最后

看了历年的难度和题型，我的结论是二分、线段树、模拟、动态规划是必须要掌握的。
练习模拟的时候，可以使用语法树题型来练习。
另外还需要掌握最基础的图论知识最短路。

对于贪心算法，需要通过分析题目寻找特征，这需要一定的逻辑能力，只能通过多做题来提升这种能力。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code