竞赛干货 | CSP-J（普及组）知识点总结

oyangningtao

一、比赛形式

普及组的考试也是分为初赛和复赛。

初赛是笔试，分为选择题，奥数题，程序阅读，程序填空。普及组的选择题降低了计算机常识的比重，增加了数据结构计算的比重，奥数题由小学组的四道题目换成了两道题目，多以逻辑思考为主。程序阅读同样采用难度递增的方式，考察顺序结构，选择结构，循环结构，数组，字符串。程序填空题多以算法为主，所以最后一道大题的得分率每年都是最低的。

复赛是机试，同样是四道题目的考察，多以模拟法，枚举法，字符串，动规为主。

普及组的考察范围虽然很广，但是对于大多数的知识点考量的不会很深。

二、常见题型和知识点

2000-2018年普及组题型统计：

1、枚举：枚举是编程最简单朴素的算法，可以理解为穷举或搜索算法，也是典型的拿分题。

2、简单动态规划；

3、数学、数论：比如质数、素数、汉诺塔、数列，这些数学知识在编程里需要用程序的方式表现，而这些数学知识相对奥数难度低了很多；

4、排序：在十大排序算法中其中又以快速排序、冒泡、堆排序最为常见；

5、模拟：当无法规则化解题时可以用模拟算法尝试；

6、字符串：编程常用类型，规范性强，是历年出题的抢手题，也是拿分题，有时字符串会和其他问题结合在一起出现；

7、搜索：从简单搜索到深度搜索各种类型都有出现；

8、贪心算法：例如历史上的排座椅、纪念品问题。

必掌握

1、模拟算法（暴力枚举），按照题目的要求，题目怎么说就怎么做，保证时间和正确性即可。

2、搜索与回溯，主要的是DFS（深度优先搜索）和BFS（宽度优先搜索），基本没有直接的暴力搜索。一般是记忆化搜索加剪枝，普及组第三题难度。

3、简单操作：如筛法、前缀和、快速幂、高精度、辗转相除法等，掌握全面即可应对大部分处理数据上的问题。

4、队列（单调队列）、栈、堆、链表等基础数据结构。

5、简单二分和分治（快速排序，归并排序）。

6、贪心，要保证贪心的正确性，如果无法证明也可以用来骗分。

7、数学知识、公式计算，要点在于公式的化简与变形，经过反复操作后也许就能得出重要结论。

8、简单的动态规划，容易推出状态转移方程，要注意初值与计算边界条件。

9、字符串基本操作，插入、删除、查找等。

10、经典例题变形加深：八皇后、马的走法、背包问题等。

三、临考技巧

1、花时间审题，选择对自己最简单的题目。题目不一定是按照难易程度排列的。

2、选中优先做的题后，不要急着写代码，先勾划一下算法流程+数据结构。

3、对于约束、边界条件，可以先不考虑，不要让这些拦住算法的整体思维。

4、不钻牛角尖，如果某一种方法不work，跳出思维，换一种方式。

5、不会的题目，特殊的边界，最后阶段暴力解决（朴素算法）“骗分”，即获得朴素分。“骗分”，其实是非完美算法（NOIP判题策略是机器输入10组左右数据检验工作） 。

暴力也有含金量！

避免低级错误

1、未包含头文件——编译检查自己的头文件！

2、主函数没有 return 0 ——写算法前先写好return 0！

3、按规范写文件名，未使用文件输入输出——写算法前先写好输入输出。

4、数值溢出，浮点精度丢失——尽量使用存储空间大的类型。

5、数组内存不够、越界——熟练数组！

6、字符串、字符、8位、16位、大小写 搞混淆——熟练字符串！

7、注意空间和时间复杂度限制！——掌握复杂度判断！