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

历年CCF-CSP认证考试题目解法思想--第1页 历年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-3 JSON查询经典字符串模拟，尤其字符\的处理很重要，注意多重嵌套的解法。 201709-4 通信⽹络 数学+DFS/BFS 201703-1 分蛋糕 简单逻辑+遍历（简单枚举） 201703-2 学⽣排队 普通list模拟 201703-3 Markdown熟悉使⽤字符串⽅法 注意设计+注释+⽅法封装 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.每次%10 2.字符串式处理） 201512-2 消除类游戏数组模拟，注意标记删除元素的⽅法 201512-3 画图 点阵模拟，读懂题意。填充部分⽤DFS的思想来处理。 201512-4 送货 欧拉通路问题。（并查集+图的数据结构+DFS）（注意先判断是否连通，再判断是否存在欧拉通路，如果 OK再DFS求路径）（数学：如何判断是否存在欧拉路径）（系统题库样例好像有问题） 201509-1 数列分段 简单枚举 201509-2 ⽇期计算数学。注意每⽉天数的存储，不要⼀直if很⿇烦。简化求解⽅法。 历年CCF-CSP认证考试题目解法思想--第1页 历年CCF-CSP认证考试题目解法思想--第2页 201509-3 模板⽣成系统null 201509-4 ⾼速公路 tarjan(求强联通分量)（需要DFS基础）（JAVA慢-10分） 201503-1 图像旋转 输出，坐标转换（数学：找规律/公式） 201503-2 数字排序 数组存储+排序就够了 201503-3 节⽇ 计算问题，注意如何存储每天天数。 201503-4 ⽹络延时 DFS（求树的直径） 201412-1 门禁系统 数组模拟 201412-2 Z字形扫描数学：找规律/公式 201412-3 集合竞价 null 201412-4 最优灌溉 并查集+优先队列/⼆维数组排序（最⼩⽣成树问题） 201409-1 相邻数对 排序+枚举 //直接枚举+vis数组 201409-2 画图 数学，学习⼀下如何去重叠⾯积就好。 201409-3 字符串匹配字符串⽅法调⽤ 201409-4 最优配餐 BFS，注意分店要放⼀起BFS，这样⼤家跑的都⼀样快，谁先遍历到谁就最近。有⼀些时间上的⼩优 化。 201403-1 相