简介面向高校计算机相关专业学生、算法竞赛入门者及准备CCF-CSP认证的编程爱好者这份资料汇编历年认证真题可用于熟悉题型结构、限时训练与查漏补缺。当前包内仅1个PDF文件压缩包约1.99MB以题目文本为主包含试题编号、名称、时间与内存限制、问题描述、输入输出格式、样例及评测用例规模等核心信息便于按年份和题号检索练习。内容节选可见数列分段、日期计算、模板生成系统、便利城市对等题目并附有提交确认要求能帮助读者贴近正式评测环境理解题意与约束条件。已有7998人学习下载。需要注意的是该资料不含答案更适合作为自测与模拟赛题使用配合个人代码实现和错题复盘逐步提升算法设计与程序调试能力。1. 只有题面没有答案的真题包它能不能支撑你一整轮机试训练CCF-CSP 认证是 4 小时 5 道题的机试历年真题的价值不在于题目多新而在于它的评测口径固定时间限制卡在 1.0s 到 5.0s内存统一 256MB输入输出契约写得明明白白连“不许输出提示语”这种细节都写进了提交确认里。这套资料收录的是 2014 年 12 月到 2015 年 9 月几场考试的完整题面从数列分段、日期计算、图像旋转这种送分题到模板生成系统、集合竞价、网络延时、便利城市对这类拉开差距的题题号、样例、评测用例规模都原样保留唯独没有参考答案和解析。它适合已经能独立写完一个带输入输出的 Java 程序、却在真实机试里反复卡在“样例过了提交 0 分”的人如果你连 Scanner 读一行都还没写过先回去把基础语法跑通再来。后面按题面结构、基础题实现、中难题建模、翻车排查四条线拆开讲每一段都能直接对着做题。2. 题面结构拆解把 1.0s 和 256MB 翻译成能落地的算法选型很多人拿到真题第一反应是打开编辑器就写写到一半发现规模是 10^5 或者 m 到了 10^15前面半小时白干。题面里真正决定你写什么的不是问题描述是最后那段“评测用例规模与约定”。这一章先把这套题的约束体系拆开让你在动手之前就能判断该用 O(n) 还是 O(n log n)该用数组还是该上矩阵快速幂。2.1 从评测用例规模倒推复杂度上限CSP 的时间限制基本按 C 给Java 选手要自己打个折。1.0s 的限制下Java 做 10^7 次简单循环差不多到顶10^8 就有风险5.0s 的题比如图像旋转看着宽松但那是给 C 留的余量Java 别真按 5 秒去设计。内存 256MB 对应 Java 堆一个 int[10000][10000] 就是 400MB直接爆掉二维矩阵题一定要先算字节数。题面中出现的规模典型题可接受的复杂度Java 侧的实现建议n ≤ 1000数列分段、数字排序、门禁系统O(n²) 以内双重循环、计数数组都行n,m ≤ 1000图像旋转、Z 字形扫描O(nm)二维数组 StringBuilder 拼输出n ≤ 10000m ≤ 100000便利城市对O(nm)邻接表 Tarjan别用邻接矩阵m ≤ 10^15最佳文章O(s³ log m)AC 自动机 矩阵快速幂这题是分水岭输入行数 ≤ 5000集合竞价O(k·n) 可接受定点数 线性扫描别上复杂数据结构这张表的用法很直接读完题先找到规模那一行对照表格定复杂度再决定数据结构。我见过太多人在便利城市对上开int[10001][10001]本地编译通过一提交就 Memory Limit Exceeded回头改成邻接表十分钟的事。提示题面里“前 30% 的评测用例满足……”这种分段描述是出题人明示的送分梯度。先把 30% 的暴力分拿到手再去想满分算法比一上来死磕正解稳得多。2.2 输入输出契约Main 类、标准流、零提示语题面最后那段“提交确认”不是客套话是硬性契约违反了直接编译错误或者 0 分。这几条必须背下来不能有 package 语句主类必须叫 Main且是 public class Main入口是 public static void main(String[] args)从 System.in 读、往 System.out 写程序里不能出现“请输入 n”这类提示也不能输出中间调试结果。一个最小可用的骨架长这样所有题都可以从它改import java.util.Scanner; public class Main { // 类名必须是 Main且不能带 package public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); // 只读题面要求的输入不打印任何提示 // 计算逻辑 System.out.println(n); // 只输出题面要求的答案 } }代码本身没什么技术含量关键在于约束类名写错一个字母就是 Compilation Error加了 package 评测机找不到入口多打印一行调试信息就是 Wrong Answer。参数上要注意 Scanner 默认按空白符切分读 int 和 long 没问题但读整行字符串必须用 nextLine()而且要小心 nextInt() 后面残留的换行符——模板生成系统那题就栽在这上面后面会细说。2.3 把历年真题按难度分成四档决定刷题顺序这套题按通过率大致能分四档不同档位的训练目标完全不同。第一档是纯模拟数列分段、门禁系统、数字排序、图像旋转考的是循环、数组、边界目标是“一次写对不调试”。第二档带一点算法味道日期计算、节日、Z 字形扫描考的是把数学规则翻译成代码的能力。第三档是真正的分水岭模板生成系统考字符串处理集合竞价考定点数和排序扫描网络延时考树上直径。第四档是拉开 300 分和 400 分的题便利城市对考强连通分量最佳文章考 AC 自动机加矩阵快速幂没有系统训练过基本写不出来。档位代表题核心考点训练目标一档数列分段、门禁系统、数字排序循环、计数、排序20 分钟内写完并自测通过二档日期计算、节日、Z 字形扫描、图像旋转日历计算、下标映射边界条件一次想全三档模板生成系统、集合竞价、网络延时字符串扫描、定点数、树直径能独立建模不靠背模板四档便利城市对、最佳文章Tarjan、AC 自动机 矩阵快速幂理解算法适用边界刷题顺序建议从一档开始按档推进而不是按年份顺序刷。同一档位的题放在一起做肌肉记忆才建立得起来跨档跳着做每次都要重新热身效率反而低。3. 基础题落地实现五道真题从题面到能提交的代码这一章挑五道一档、二档的题每道给出完整可提交的 Java 实现重点不在代码本身在于代码背后的边界处理。这些题看着简单但每年都有大量人在这上面丢分原因基本都是“样例过了就以为对了”。3.1 数列分段一趟扫描和它的初始化陷阱题目要求把连续相同的整数算成一段问总共有几段。思路很朴素从左到右扫一遍当前元素和上一个元素不同就说明进入新的一段。坑在初始值如果prev初始化为 0而数列第一个元素正好是 0第一段就会被漏掉。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int prev -1; // 题面保证 ai 0用 -1 占位保证首元素必开新段 int seg 0; // 段数计数 for (int i 0; i n; i) { int cur in.nextInt(); if (cur ! prev) { // 与上一元素不同说明进入新的一段 seg; prev cur; } } System.out.println(seg); } }逻辑说明循环里只做一次比较时间复杂度 O(n)空间 O(1)。prev的初值选取是整个解法的关键用 -1 是因为题面限定0 ≤ ai ≤ 1000负数不可能出现在输入里。参数说明n 最大 1000完全在 int 范围内不需要 long。如果题目没给 ai 的非负约束就得换一种写法比如单独处理 i0 的情况或者用一个 boolean 标记是否已经读过第一个元素。这题还有一个容易忽略的点输入是“第二行包含 n 个整数”但用 Scanner 读的时候根本不用管行nextInt() 会自动跳过换行和空格。新手常犯的错是先 nextLine() 读整行再 split结果第一行读 n 之后残留的换行符把第二行读成空串直接抛异常。3.2 日期计算与节日闰年判定和星期推算的统一工具日期计算给年份 y 和整数 d问这一年第 d 天是几月几日。核心就两件事闰年判定以及月份天数表。闰年规则题面写得很清楚能被 4 整除且不能被 100 整除或者能被 400 整除。很多人写成y % 4 0就完事1900 年这种整百年份立刻翻车。import java.util.Scanner; public class Main { static boolean isLeap(int y) { // 完整闰年规则4 的倍数且非 100 的倍数或 400 的倍数 return (y % 4 0 y % 100 ! 0) || y % 400 0; } public static void main(String[] args) { Scanner in new Scanner(System.in); int y in.nextInt(), d in.nextInt(); int[] days {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) days[1] 29; // 闰年二月改 29 天 int m 0; while (d days[m]) { // 逐月扣减直到剩余天数落在当月 d - days[m]; m; } System.out.println((m 1) \n d); // 月份从 0 开始输出要加 1 } }逻辑说明days数组下标 0 对应一月循环扣减直到 d 不大于当月天数此时 m 就是目标月份的下标d 就是日。参数说明y 在 1900 到 2015 之间d 在 1 到 365 之间int 完全够用。输出是两行先月后日用\n拼在一个 println 里比两次 println 更稳避免有人误加空行。节日那题是它的进阶版给定 a 月第 b 个星期 c输出 y1 到 y2 每年的日期。这题的关键是知道 1850 年 1 月 1 日是星期二然后推任意一天是星期几。我一般的做法是写一个weekdayOf(y, m, d)函数把从 1850 年到目标日期的总天数算出来再对 7 取模// 返回星期编号1周一2周二 ... 7周日 static int weekdayOf(int y, int m, int d) { long diff 0; for (int i 1850; i y; i) diff isLeap(i) ? 366 : 365; int[] md {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) md[1] 29; for (int i 0; i m - 1; i) diff md[i]; diff d - 1; // 到目标日期经过的天数 return (int) ((diff 1) % 7 1); // 1850-01-01 是周二偏移后映射到 1..7 } // 求 y 年 a 月第 b 个星期 c 的日号不存在返回 -1 static int nthWeekday(int y, int a, int b, int c) { int w1 weekdayOf(y, a, 1); // 该月 1 号是星期几 int offset ((c - w1) % 7 7) % 7; // 1 号之后第一个星期 c 的偏移 int day 1 offset 7 * (b - 1); int[] md {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; int maxDay md[a - 1] (a 2 isLeap(y) ? 1 : 0); return day maxDay ? day : -1; // 超出当月天数说明不存在 }逻辑说明offset那行用((c - w1) % 7 7) % 7而不是直接取模是因为 Java 的%对负数返回负值c 比 w1 小的时候会算出负数天。参数说明年份范围 1850 到 2050diff用 long 是防御性写法虽然这个范围 int 也够。样例 5 2 7 2014 2015 输出 2014/05/11 和 2015/05/10可以自己代进去验算2014 年 5 月 1 日是周四5 月 11 日正好是第二个周日。这题输出格式要求“位数不足前补零”用String.format(%04d/%02d/%02d, y, a, day)最省事手写补零容易在月份和日期上漏掉分支。3.3 矩阵下标映射图像旋转与 Z 字形扫描的两个方向图像旋转要求把 n 行 m 列的矩阵逆时针转 90 度输出 m 行 n 列。这题的难点不是算法是下标映射别推错。原矩阵 a[n][m]新矩阵 b[m][n]逆时针转 90 度后原来的右上角跑到左上角映射关系是b[i][j] a[j][m-1-i]。这个式子建议在纸上画个 2×3 的矩阵推一遍比死记靠谱。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(), m in.nextInt(); int[][] a new int[n][m]; for (int i 0; i n; i) for (int j 0; j m; j) a[i][j] in.nextInt(); StringBuilder sb new StringBuilder(); for (int i 0; i m; i) { // 新矩阵 m 行 for (int j 0; j n; j) { // 新矩阵 n 列 if (j 0) sb.append( ); sb.append(a[j][m - 1 - i]); // 核心映射逆时针 90 度 } sb.append(\n); } System.out.print(sb); // 一次性输出避免多次 IO } }逻辑说明双重循环按新矩阵的行列遍历每个位置反查原矩阵。参数说明n、m 最大 1000矩阵总元素 10^6用 Scanner 逐个读会偏慢但 5.0s 的限制下能过更快的写法是 BufferedReader 加自定义切分属于进阶优化后面最后一章会提。输出用 StringBuilder 拼完整再打印是因为 10^6 个数字用 System.out.println 逐个输出会触发大量 IO实测能差出好几倍时间。Z 字形扫描是另一种映射按对角线走。观察样例能发现规律把所有ij相同的元素归为一条对角线编号 s 从 0 到 2n-2s 为偶数时从下往上走s 为奇数时从上往下走。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int[][] a new int[n][n]; for (int i 0; i n; i) for (int j 0; j n; j) a[i][j] in.nextInt(); StringBuilder sb new StringBuilder(); for (int s 0; s 2 * n - 2; s) { int rLo Math.max(0, s - (n - 1)); // 该对角线上最小行号 int rHi Math.min(s, n - 1); // 该对角线上最大行号 if (s % 2 0) { // 偶数对角线从下往上 for (int r rHi; r rLo; r--) sb.append(a[r][s - r]).append( ); } else { // 奇数对角线从上往下 for (int r rLo; r rHi; r) sb.append(a[r][s - r]).append( ); } } System.out.println(sb.toString().trim()); // trim 去掉末尾多余空格 } }逻辑说明rLo和rHi把行号限制在矩阵范围内避免越界列号直接用s - r算出来不用另外维护。参数说明n 最大 500总元素 250000O(n²) 完全够。trim()那一下不能省否则最后会多一个空格部分评测点会判格式错误。这题的方向判断是最容易错的地方建议拿样例的 4×4 矩阵手推一遍 s0 到 s6确认偶数从下往上之后再去写代码。3.4 数字排序计数数组和比较器排序的取舍数字排序要求按出现次数从多到少输出次数相同按数值从小到大。题面给的数不超过 1000这个范围直接决定了用计数数组比用 HashMap 加比较器更简单也更快。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int n in.nextInt(); int[] cnt new int[1001]; // 数值范围 0..1000 for (int i 0; i n; i) cnt[in.nextInt()]; StringBuilder sb new StringBuilder(); for (int c n; c 1; c--) { // 外层按出现次数从大到小 for (int v 0; v 1000; v) { // 内层按数值从小到大 if (cnt[v] c) sb.append(v).append( ).append(c).append(\n); } } System.out.print(sb); } }逻辑说明外层枚举出现次数内层枚举数值天然满足“次数降序、数值升序”的双关键字要求不需要写比较器。参数说明n 最大 1000内层固定 1001 次总循环次数最多 10^6 量级稳过。如果数值范围没给比如到 10^9这套写法就不成立了得换成MapInteger,Integer加List排序比较器要写成先比次数再比值// 数值范围很大时的写法先按次数降序次数相同按数值升序 list.sort((x, y) - { if (!x.getValue().equals(y.getValue())) return y.getValue() - x.getValue(); return x.getKey() - y.getKey(); });两种写法的差别不只是代码长短。计数数组是 O(n V)V 是值域比较器排序是 O(k log k)k 是不同数值的个数。值域小的时候前者快一个数量级值域大的时候后者才可用。这种“看约束选数据结构”的判断比记住某个模板重要得多。4. 中高难度题的建模路径字符串、撮合与树上的距离三档以上的题难点从“写对”变成“想清楚”。这一章挑三道有代表性的模板生成系统考整行读入和占位符扫描集合竞价考定点数和排序撮合网络延时考树上直径。每道题都会把建模过程写出来而不只是贴代码。4.1 模板生成系统整行读入、占位符扫描和三个隐藏边界题目给 m 行模板和 n 个变量要求把模板里的{{ VAR }}替换成变量值未定义的变量替换成空串且不递归替换。这题的输入格式是最大的坑模板行里可能有空格、可能有空行必须用 nextLine() 整行读绝对不能用 next()。import java.util.*; public class Main { public static void main(String[] args) { Scanner in new Scanner(System.in); int m in.nextInt(), n in.nextInt(); in.nextLine(); // 吃掉 m n 后面的换行否则第一行模板读成空串 String[] tpl new String[m]; for (int i 0; i m; i) tpl[i] in.nextLine(); // 模板必须整行读 MapString, String vars new HashMap(); for (int i 0; i n; i) { String line in.nextLine(); int sp line.indexOf( ); // 第一个空格分隔变量名和值 String key line.substring(0, sp); String val line.substring(sp 1).trim(); val val.substring(1, val.length() - 1); // 去掉首尾双引号 vars.put(key, val); } StringBuilder out new StringBuilder(); for (String line : tpl) { int i 0; while (i line.length()) { int l line.indexOf({{, i); if (l 0) { out.append(line, i, line.length()); break; } out.append(line, i, l); // 先拼标记之前的普通文本 int r line.indexOf(}}, l 2); String key line.substring(l 2, r).trim(); // trim 掉标记内空格 out.append(vars.getOrDefault(key, )); // 未定义变量替换为空串 i r 2; } out.append(\n); } System.out.print(out); } }逻辑说明对每一行模板做一次从左到右的扫描遇到{{就把前面的普通文本拼进去再找配对的}}取出中间的变量名去哈希表查值查不到就用空串。参数说明m 是模板行数n 是变量个数变量名长度不超过 16值用双引号括起来且可能含空格。三个容易翻车的边界in.nextLine()前必须先吃掉换行变量名两边可能有空格取值前要 trim变量值首尾的引号必须去掉但值内部的空格要保留。第三点最容易错如果直接用split(\)取值值里本身带引号就崩了虽然题面说值里不含引号但用 substring 切首尾更稳。注意题面明确写了“模板不递归生成”也就是变量值里即使出现{{ xxx }}也不再替换。用上面这种一次性扫描的写法天然满足这个约束如果写成循环替换直到没有标记反而会死循环或者错误递归。4.2 集合竞价撤单标记、定点数和撮合扫描这题是整套题里最考工程思维的一道。输入若干条 buy、sell、cancel 记录cancel i 表示撤销第 i 行的记录要你找一个开盘价使得成交量最大成交量相同取价格最高的。成交量定义是所有出价不低于开盘价的买单总股数和所有出价不高于开盘价的卖单总股数取较小值。第一个决策是价格怎么存。题面说“出价为精确到恰好小数点后两位的正实数”用 double 算 9.25 乘 100 可能得到 924.9999999转 int 就变成 924。正确做法是按字符串切小数点把价格转成分// 把 9.25 这类两位小数价格转成分避免浮点误差 static long toCents(String s) { int dot s.indexOf(.); String intPart s.substring(0, dot); String frac (s.substring(dot 1) 00).substring(0, 2); // 补足两位 return Long.parseLong(intPart) * 100 Long.parseLong(frac); }逻辑说明整数部分乘 100 加小数部分全程整数运算没有精度损失。参数说明价格不超过 10000.00转成分之后最大 1000000long 绰绰有余股数不超过 10^8多个订单累加可能溢出 int必须用 long。第二个决策是撤单怎么处理。cancel i 里的 i 是输入行号从 1 开始而且被撤销的那条记录可能本身也是一条 cancel。我一般的做法是先把所有记录读进 List再扫一遍打失效标记// 第一遍把所有被 cancel 指向的记录标记为失效 for (int i 0; i list.size(); i) { Order o list.get(i); if (o.type 2) { // 2 表示撤单 list.get(o.cancel - 1).alive false; // 行号 1-based 转 0-based o.alive false; // 撤单记录本身也不参与撮合 } }第三个决策是撮合怎么算。输入行数不超过 5000可以对每个出现过的价格线性扫一遍所有订单复杂度 O(k·n)最坏 2.5×10^7Java 一秒内能过。核心逻辑是对候选价格 p0累加所有price p0的买单股数和所有price p0的卖单股数取 min 就是成交量所有候选价格里取成交量最大、价格最高的那个。long bestVol 0, bestPrice 0; for (Order cand : list) { if (!cand.alive || cand.type 2) continue; // 跳过失效单和撤单记录 long p0 cand.price, buy 0, sell 0; for (Order o : list) { if (!o.alive) continue; if (o.type 0 o.price p0) buy o.vol; // 买单出价不低于开盘价 if (o.type 1 o.price p0) sell o.vol; // 卖单出价不高于开盘价 } long v Math.min(buy, sell); // 成交量更大或成交量相同但价格更高时更新答案 if (v bestVol || (v bestVol p0 bestPrice)) { bestVol v; bestPrice p0; } } System.out.printf(%.2f %d%n, bestPrice / 100.0, bestVol);逻辑说明双重循环枚举候选价格内层累加买卖盘。参数说明bestPrice初始为 0bestVol初始为 0如果所有价格成交量都是 0 会输出0.00 0题面保证有合法撮合正常不会走到这个分支。输出用printf(%.2f)保证两位小数用bestPrice / 100.0还原这里除法是唯一一次浮点运算只影响输出格式不影响比较。这题我踩过的最深的坑是撤单的行号语义cancel i 里的 i 指的是输入的第 i 行包括前面的 cancel 行本身。一开始我以为是撤销第 i 条有效订单结果样例都过不了。题面里“撤销第 i 行的记录”这句话读三遍别想当然。4.3 网络延时与便利城市对树直径和强连通分量网络延时给一棵树交换机编号 1 到 n电脑编号接在后面问任意两点间最远距离。这是标准的树直径问题结论是从任意点出发找到最远点 u再从 u 出发找到最远点 vu 到 v 的距离就是直径。证明不用背记住两次 BFS 就行。// 从 start 出发 BFS返回 {最远节点, 最远距离} static int[] bfs(int start, int total) { int[] dist new int[total 1]; Arrays.fill(dist, -1); // -1 表示未访问 DequeInteger q new ArrayDeque(); dist[start] 0; q.add(start); int far start; while (!q.isEmpty()) { int u q.poll(); if (dist[u] dist[far]) far u; for (int v : g.get(u)) { if (dist[v] -1) { // 首次访问才入队树无环不会重复 dist[v] dist[u] 1; q.add(v); } } } return new int[]{far, dist[far]}; }逻辑说明BFS 保证首次到达就是最短距离树上没有环不需要判重集合一个 dist 数组足够。参数说明total n m交换机占 1 到 n电脑占 n1 到 nm统一编号后整棵树就是一个无向图。主函数里读入时要注意第二行是 n-1 个整数表示第 2 到 n 台交换机的上级第三行是 m 个整数表示电脑连的交换机用 Scanner 直接顺序读即可不用按行处理。这里必须提醒n 最大可能到 10^4 量级递归 DFS 在这棵树上可能爆栈Java 默认栈深度撑不住一万层。用 BFS 或者显式栈的迭代 DFS 更稳别图省事写递归。便利城市对是另一个方向给有向图本文还有配套的精品资源点击获取