字符串处理上：lcs(最长公共子序列)，kmp
（字符串匹配算法），复杂题设计思维+注释，
类的设置，数据封装，多重嵌套解法。
图论算法上（目前出现过的）：设置高效的邻
接表，dfs 是基础，bfs（最优/短问题且各边
权值为 1），djs+Floyd（最短路径问题），
欧拉通路/回路判断，树的直径问题，tarjan
（强联通分量问题），并查集（判断是否连
通），prim+kruskal（最小生成树问题），
拓扑排序、动态规划基本没怎么出现过。
第一题：水题（稍微有些编程经验就可以写）
第二题：小模拟（处理比较简单的问题，掌握 C+
+STL 很有帮助）
第三题：大模拟（处理复杂的问题，一般涉及文
本处理，需要熟练掌握 C++STL 并且细心）
第四题：算法题（难度一般，重点考图论算法和
动态规划）
第五题：算法题（难度很高，涉及算法面很多，
而且数据量很大，需要对算法极致优化，很难满
分）
历年 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 很麻烦。简化求解方法。
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 数
评论0