CCF-CSP历年真题大全附题解(202309已更)

CCF-CSP真题拿来练手，持续更新，CCF-CSP真题拿来练手，如果对自己没有拿高分的期望的话，可以就琢磨着写一二三题就好，三题和四题可以稍微瞧一瞧，可以就拿最基础的情况，再慢慢添东西更新代码。博主的算力有限，努力提升进步中，写一道发一道，目前先从简单慢慢做，有想法的可以一起讨论呀~~

文章末放着CCF-CSP真题网站，有需要的同学自取~~

• 第一题看起来复杂，实际上只要把输入的每个棋盘的棋子保存到字符数组中，然后判断这个字符串在map中是否出现过，若出现过，则出现次数加一，否则记录这个字符串的出现次数为1就行了。
• 这道题也不难，再纸上推一下规律就能找到循环去计算的规律。这道题的重点在于时间复杂度，如果先算QK矩阵相乘，会得到n * n的矩阵，会显示超时，所以要先算后面两个矩阵，时间复杂度是可以过的。
• 题目给我们一段压缩过的代码，可以拆分为引导域和数据域，引导域决定了解压缩后的数据长度，数据域也是可以分段的，每一段由其第一个字节的最低两位决定，若为00，则是字面量，若为01或10，则为回溯引用。输出解压缩后的数据，8字节为一行，最后一行允许不到8个字节。由于要多次读取字节，所以最好封装一个函数来 读取字节 ，记录当前读到的位置。由于要进行小端序调整字符串，可以考虑封装一个函数来 按小端序调整字符串 。由于01和10结尾都要回溯引用，也可以封装一个函数来 填充字符串 。由于用字节处理太麻烦了，可以使用 stoi()——有符号整型 或者 stoul——无符号整型 来进行进制转换。

• 第一题主要是求所圈的矩阵和其他已有矩阵的交集面积，交际面积的右边界即两个相交矩阵的最右边的边界，即min(a, points[i][2])，左边界即两个相交矩阵的最右边的边界，即max(0, points[i][0])。上下边也是一样的道理。通过判断x 和 y是否大于零，可以判断出矩阵十分交叉，若存在则 sum += x * y；
• 第二题也不难，使用标志数组记录耗时为i天的区域降低一天的总花费，然后从高向低降，最后就可以得出答案了。
• 第三题主要解决表达式嵌套的问题，与栈实现计算器时维护一个符号栈、一个数值栈类似。这里维护了两个栈，一个符号栈op，一个bitset集合栈stk，集合求交、或，由bitset完成。当遇到&或|时，将符号压栈；当遇到)时，将bitset压栈；()内正常读取，求bitset即可。
• 第四题属于线段树（离散化、单点询问、区间求和、区间最值）的经典题。线段树维护区间和，用于记录对应区间几个值被用过，且线段树维护最大最小值，用于记录被哪个用户id用过，当最小值=最大值时，表示恰被一个用户用过。首先，将最大32维的数转10进制，压成长为32的array，离散化去重后，找到每个ip地址对应下标映射。
• 第五题用的是分治+线段树+树状数组。

• 第一题我直接理解题目后应用公式进行求解，暴力解是可以满分的；
• 第二题我看了一下，由于70% 的测试数据满足：顿顿无法在n天内完成全部m项科目的训练，此时不需要考虑最晚开始时间是否输出的问题，直接输出最早开始时间即可得70分，而在最晚开始时间的计算中，由于某科目是被别的科目依赖的，所以计算它的最晚开始时间时要考虑依赖它的科目能否如期完成。

202209的真题

• 第一题我直接应用题目公式进行了变幻求解，暴力解是可以满分的；
• 第二题我第一眼看过去感觉就可以用动态规划等常规算法去解，题目看着有点像01背包问题，但我最先还是用的暴力解，情况考虑少了，只得70分，后面仔细分析了下动态规划的规律，用动态规划的方法重新写了一遍，满分题解；
• 第三题感觉应该是读题比较难，建议那个笔写一遍捋一下情况，每个值是干嘛的搞清楚才开始写，目前是40分的代码，后续进行修改；
• 第四题看了一眼感觉很容易理解，也就直接直白写了，果不其然内存超了，拿了20分；

202206的真题

• 第一题我直接应用题目公式进行了变幻求解，暴力解是可以满分的；
• 第二题我考试时先用的暴力解，遍历整个绿化图，最后很明显内存超了，后面思考了一下，只需要一藏宝图为参照目标，将绿化图中的树的位置记录，然后再进行判断筛选，就可以简单的得出结果，这样还避免了暴力解中超内存的情况的出现。
• 第三题只想拿20分就照着子任务中的第一种情况去写的，拿20分对大多数人来说还是很容易的，只要把题读明白就好；满分则需要进行分析。

202203的真题

• 第一题我用的set去进行数据的存储，边存边进行去重，然后按照题目进行编写就好了；
• 第二题我还是用的暴力解去做了一遍题目，只要暴力解过了，说明你对题目的理解就到位了，很明显暴力解双重循环时间上暴了，所以我们要进行优化。最后使用差分数组，每个出行计划就是对有效区间的操作。最后前缀和统计一下，随后查询即可；
• 第三题我是直接看着子任务中的第一种情况去写的，因为我的目的就是拿20就好，拿20分对大多数人来说还是很容易的，只要把题读明白就好；

202111的真题

202109的真题

202104的真题

202012的真题

202009的真题

有想法的朋友可以自己去网站进行实践：csp真题网站 – 计算机软件能力认证考试系统