历年CCF-CSP认证考试题目解法思想 .pdf

历年CCF-CSP认证考试题⽬解法思想

每年的题难度都不太⼀样，这⼀点在16、17年上尤其明显，难度低的时候前两道题就是送分题，加⼀起15分钟解决，得分

样例⽔的不⾏。难度⾼的时候第⼆题就让你模拟半天，且测试样例诡异⽆⽐，测试样例通过可能只=20分，就别说后⾯3,4

题了。

总结⼀些技术点、难点：

字符串处理上：lcs(最长公共⼦序列)，kmp（字符串匹配算法），复杂题设计思维+注释，类的设置，数据封装，多重嵌套

解法。

图论算法上（⽬前出现过的）：设置⾼效的邻接表，dfs是基础，bfs（最优/短问题且各边权值为1），djs+Floyd（最短路

径问题），欧拉通路/回路判断，树的直径问题，tarjan（强联通分量问题），并查集（判断是否连

通），prim+kruskal（最⼩⽣成树问题），拓扑排序、动态规划基本没怎么出现过。

历年CCF-CSP认证考试题⽬解法/思想：

201709-1打酱油贪⼼+数学

201709-2公共钥匙盒排序+数组模拟，分析好如何安排时间

201709-3JSON查询经典字符串模拟，尤其字符\的处理很重要，注意多重嵌套的解法。

201709-4通信⽹络数学+DFS/BFS

201703-1分蛋糕简单逻辑+遍历（简单枚举）

201703-2学⽣排队普通list模拟

201703-3Markdown熟悉使⽤字符串⽅法注意设计+注释+⽅法封装

201703-4地铁修建并查集+优先队列/⼆维数组排序（JAVA慢-10）

201612-1中间数简单排序+数学逻辑（找规律）

201612-2⼯资计算枚举（正推+检索——求解思想）（注意给的数据类型、⼤⼩，注意到S是100的倍数，枚举时间在可

控范围内）

201612-3权限查询字符串处理+数据封装（注意数据之间嵌套严重，所以要⼩⼼设计类和List，最好草稿纸上先设计好再

动⼿。注意对⼀些复⽤⽅法进⾏封装）

201612-4压缩编码null

201609-1最⼤波动简单枚举

201609-2⽕车购票贪⼼+遍历，⽤数组/map模拟

201609-3炉⽯传说同201612-3但相对要简单，嵌套不那么严重，处理好数据就可以模拟了

201609-4交通规划djs（单源最短路径）+变形（基础上进⾏优化）

201604-1折点计数简单枚举

201604-2俄罗斯⽅块简单数组模拟

201604-3路径解析字符串处理（想好可能需要处理哪些情况，分类处理）

201604-4游戏BFS（最短问题且结点连通权值为1）+变形（考虑格⼦与时间的关系）

201512-1数位之和解题⽅法选择（1.每次%102.字符串式处理）

201512-2消除类游戏数组模拟，注意标记删除元素的⽅法

201512-3画图点阵模拟，读懂题意。填充部分⽤DFS的思想来处理。

201512-4送货欧拉通路问题。（并查集+图的数据结构+DFS）（注意先判断是否连通，再判断是否存在欧拉通路，如果

OK再DFS求路径）（数学：如何判断是否存在欧拉路径）（系统题库样例好像有问题）

201509-1数列分段简单枚举

201509-2⽇期计算数学。注意每⽉天数的存储，不要⼀直if很⿇烦。简化求解⽅法。

201509-3模板⽣成系统null

201509-4⾼速公路tarjan(求强联通分量)（需要DFS基础）（JAVA慢-10分）

201503-1图像旋转输出，坐标转换（数学：找规律/公式）

201503-2数字排序数组存储+排序就够了

201503-3节⽇计算问题，注意如何存储每天天数。

201503-4⽹络延时DFS（求树的直径）

201412-1门禁系统数组模拟

201412-2Z字形扫描数学：找规律/公式

201412-3集合竞价null

201412-4最优灌溉并查集+优先队列/⼆维数组排序（最⼩⽣成树问题）

201409-1相邻数对排序+枚举//直接枚举+vis数组

201409-2画图数学，学习⼀下如何去重叠⾯积就好。

201409-3字符串匹配字符串⽅法调⽤

201409-4最优配餐BFS，注意分店要放⼀起BFS，这样⼤家跑的都⼀样快，谁先遍历到谁就最近。有⼀些时间上的⼩优

化。

201403-1相反数数学统计，map处理//数据处理（负的变正）+排序+枚举

201403-2窗⼝模拟，主要是如何安排数据

201403-3命令⾏选项字符串处理，注意⽅法