简介这份CCF-CSP认证考试历年真题面向准备参加CCF计算机软件能力认证的在校学生、算法学习者与竞赛入门选手核心用途是借助原题文本熟悉认证考试的题型结构、难度梯度与提交规范。压缩包共1个PDF文件大小约1.99MB集中收录历年试题的完整题面包括问题描述、输入输出格式、样例说明、评测用例规模与约定等便于按年份和试题编号检索练习。需要说明的是文件中不含参考答案更适合用作自测与模拟训练材料。借助这些原题读者可以还原真实考试场景训练数列分段、日期计算、模板生成、图论计数等常见题型的建模与编码思路也能对照时间与内存限制检查程序效率。目前已有7998人学习适合作为备考阶段的基础题库与查漏补缺资料。1. CSP 认证历年真题怎么刷从“会写”到“能过评测”的三道门槛CSP 认证考试历年真题里最容易被低估的不是最后一道压轴题而是第一题旁边的“提交确认”。很多人平时刷题能写出思路一到评测就翻车主类名不是Main、程序里多了一句“请输入 n”、结果中间顺手打印了调试数组最后全部判错。这场考试真正考的是三件事能不能把题意翻译成稳定代码能不能在 1.0s 和 256MB 的限制里选对数据结构能不能严格遵守标准输入输出。这套 2014、2015 年的真题合集只有题面、不含答案正好逼你把每道题的判定依据写出来而不是看完题解就产生“我会了”的错觉。适合正在准备认证考试的人也适合拿它练校招笔试基础题的人。先别急着攻图论和动态规划把数列分段、门禁系统、日期计算、图像旋转这几类题刷到一次提交就过后面的分数才有意义。2. 基础模拟数列分段、门禁系统、模板生成的三类送分骨架基础题的分值不是“白送”而是用来筛掉读题不细、输出格式不稳的人。这一章挑三道很典型的题一道只看相邻元素一道考计数数组一道考字符串的一次替换。它们看起来不像同一个模块但答题骨架一致先把输入范围看清楚再决定用数组还是映射最后只输出题目要求的那个结果。下面每道题都给一段可提交风格的 Java 代码重点看注释和参数范围不要只背循环。2.1 数列分段相邻不同才切一刀题面说“连续相同的最长整数序列算成一段”这句话已经把算法说完了只需要比较当前数和前一个数不同就段数加一。样例里8 8 8 0 12 12 8 0的答案是 5不是 4因为最后的8和前面的8中间隔了0和12不能合并。很多人第一反应是统计不同数字的个数样例一跑就发现对不上。这个题的数据范围是1 ≤ n ≤ 10000 ≤ ai ≤ 1000用Scanner足够不需要建哈希表。注意n 1时答案应为 1循环不能从 0 开始又把第一项算一次。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int prev sc.nextInt(); // 第一项先读进来作为当前段的基准 int segments 1; // n 1至少有一段 for (int i 1; i n; i) { int cur sc.nextInt(); if (cur ! prev) { // 只和相邻项比较不是和前面所有项比较 segments; prev cur; // 新段从当前数开始 } } System.out.println(segments); } }这段代码里prev承担的是“当前段最后一个值”的角色。如果cur prev说明还在同一段里什么都不做如果不等说明段断了计数器加一同时把基准换成cur。时间复杂度是O(n)空间复杂度是O(1)。易错点有两个一是把“连续相同”理解成“整个数组里相同值只算一次”二是忘了n 1的初始值。评测时只输出一个整数不要打印“段数是”这种提示语。2.2 门禁系统计数数组比 Map 更稳这道题问每条记录中的读者编号是第几次出现。输入保证读者编号是不超过n的正整数这就给了很明确的信号可以直接开一个长度为n 1的计数数组。每读到一个编号id就执行cnt[id]然后输出cnt[id]。如果编号范围没有这么规整才需要考虑HashMap。基础题里能开数组就开数组数组的常数小、不会因为哈希冲突或装箱拖慢速度。输出要求是一行n个整数用空格分隔最后一个数后面不要多打一个空格更稳妥。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cnt new int[n 1]; // 题目保证读者编号不超过 n StringBuilder out new StringBuilder(); for (int i 0; i n; i) { int id sc.nextInt(); cnt[id]; // 当前编号出现次数加一 if (i 0) out.append( ); out.append(cnt[id]); // 输出的是“第几次出现” } System.out.println(out); } }参数含义很直接n是记录条数cnt[id]是编号id到目前为止出现的次数。用StringBuilder是为了避免在循环里反复拼接字符串。这里有一个小检查如果题目没有保证编号不超过n这段代码会数组越界那时才改成MapInteger, Integer。考试时先看“评测用例规模与约定”这句话比题面故事更有用。输出时不要输出每条记录的原始编号题目要的是出现次数。2.3 模板生成系统一次替换不递归模板生成系统考的是字符串处理但真正容易错的是替换规则。变量名由大小写字母、数字和下划线构成第一个字符不能是数字长度不超过 16变量名区分大小写标记里的变量未定义时替换成空串模板不递归生成也就是说变量的值里如果又出现{{ VAR }}不能再替换。最后这一条决定了不能用“按变量逐个replace”的写法因为前一次替换插入的值可能被后一次替换误伤。更稳的做法是用正则一次扫描模板行遇到标记就查映射表没查到就写空串。import java.util.*; import java.util.regex.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); // 模板行数 int n sc.nextInt(); // 变量个数 sc.nextLine(); String[] tpl new String[m]; for (int i 0; i m; i) { tpl[i] sc.nextLine(); } MapString, String vars new HashMap(); for (int i 0; i n; i) { String line sc.nextLine(); int sp line.indexOf( ); String key line.substring(0, sp); // 值用双引号包住去掉首尾两个引号值内部可能含空格 String val line.substring(sp 2, line.length() - 1); vars.put(key, val); } // 变量名首字符不能是数字总长度不超过 16 Pattern p Pattern.compile(\\{\\{\\s*([A-Za-z_][A-Za-z0-9_]{0,15})\\s*\\}\\}); for (String line : tpl) { Matcher mat p.matcher(line); StringBuffer sb new StringBuffer(); while (mat.find()) { String key mat.group(1); String val vars.getOrDefault(key, ); // 未定义变量替换为空串 // 变量值里可能有 $ 或 \必须 quoteReplacement mat.appendReplacement(sb, Matcher.quoteReplacement(val)); } mat.appendTail(sb); System.out.println(sb.toString()); } } }这段代码的关键参数是正则里的\\s*和{0,15}。\\s*允许{{ name }}这种花括号和变量名之间有空格的形式{0,15}表示变量名首字符之外最多再跟 15 个字符总长度不超过 16。Matcher.quoteReplacement不能省因为变量的值可以是除双引号外的任意可打印 ASCII 字符其中可能包含$和反斜杠直接拼进替换串会被正则当成特殊符号。还一个细节题目说模板不递归所以一次find扫描只处理模板原文里的标记插入的值不再进入下一轮匹配。若变量未定义getOrDefault返回空串相当于把标记删除。输出时每一行模板都要输出哪怕这一行没有变量。3. 日期与矩阵闰年、星期推算、旋转和 Z 字形扫描的硬骨头日期题和矩阵题在真题里出现得很稳定因为它们不依赖复杂算法却能同时考边界、下标和格式。日期题的核心不是写一堆if而是把闰年规则、月份天数、星期起点拆成可复用的函数矩阵题的核心不是背旋转公式而是先写出“新矩阵的第i行第j列对应原矩阵的哪个位置”。这一章用日期计算、节日推算、图像旋转和 Z 字形扫描四个点把这类题的答题顺序固定下来先定基准再推公式最后校验下标范围。3.1 日期计算月份前缀表比一堆 if 稳题面给年份y和整数d问这一年的第d天是几月几日。闰年规则写得很清楚年份是 400 的整数倍或者年份是 4 的整数倍且不是 100 的整数倍。注意1900不是闰年2000是闰年这两个年份经常被拿来当边界。实现时先建一个平年月份天数数组判断闰年后把二月改成 29然后让d依次减去每个月的天数直到d小于等于当前月天数。输出两行第一行月份第二行日期。import java.util.Scanner; public class Main { static boolean isLeap(int y) { return y % 400 0 || (y % 4 0 y % 100 ! 0); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int y sc.nextInt(); int d sc.nextInt(); int[] days {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) days[1] 29; // 闰年二月 29 天 int mon 0; // 数组下标最后输出 mon 1 while (d days[mon]) { d - days[mon]; mon; } System.out.println(mon 1); System.out.println(d); } }参数说明y的范围是 1900 到 2015d的范围是 1 到 365。mon从 0 开始因为数组下标从 0 开始输出月份时要加一。d在循环里被不断减去整月天数剩下的就是当月第几天。这段代码的时间复杂度是O(12)可以忽略。易错点是闰年判断写成y % 4 0就结束导致 1900 年被当成闰年另一个是输出格式题目要求两行两个整数不要输出成3/21这种形式。3.2 节日先算月首星期再推第 b 个星期 c节日题给a, b, c, y1, y2要求输出每年a月的第b个星期c的日期不存在就输出none。题面还给了一个重要基准1850 年 1 月 1 日是星期二。这类题不要一上来就写循环翻日历先算目标年份a月 1 日是星期几再算第一个星期c出现在几号。设c用 1 到 7 表示星期一到星期日月首星期为w那么第一个星期c的日期是1 (c - w 7) % 7第b个就是在这个基础上加(b - 1) * 7。如果结果超过当月天数输出none。static int weekdayOfFirstDay(int y, int a) { // 返回 1周一 ... 7周日 int days 0; for (int year 1850; year y; year) { days isLeap(year) ? 366 : 365; } int[] mon {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) mon[1] 29; for (int i 0; i a - 1; i) { days mon[i]; } // 1850-01-01 是星期二所以先加 1 再取模最后加 1 映射到 1..7 return ((days 1) % 7) 1; }这段函数只算月首星期后面的日期推算放在主流程里。days表示从 1850 年 1 月 1 日到目标年a月 1 日前一天的总天数。公式((days 1) % 7) 1的推导可以用一个点校验days 0时返回 2正好是星期二。得到月首星期w后第一个星期c的日期为1 (c - w 7) % 7。如果这个日期大于当月天数说明这个月没有第b个星期c。输出格式要求四位年份、两位月份、两位日期中间用斜杠分隔位数不足前补零。可以用String.format(%04d/%02d/%02d, y, a, day)不要手动拼字符串漏零。3.3 图像旋转与 Z 字形扫描先定坐标再写循环图像旋转题要求把一个n行m列的矩阵逆时针旋转 90 度。直接背“新矩阵第 i 行第 j 列等于原矩阵第 j 列第 n-1-i 行”容易绕晕更稳的写法是看输出顺序逆时针旋转后共有m行每一行对应原矩阵的一列而且是从最后一列开始列内从上到下。所以外层循环让原列j从m - 1到 0内层循环让原行i从 0 到n - 1依次输出a[i][j]。样例2 3的矩阵旋转后输出3 4 / 5 2 / 1 3用这个顺序一对就明白。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] a new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { a[i][j] sc.nextInt(); } } // 逆时针 90 度按原矩阵的列从右到左输出每列从上到下 for (int j m - 1; j 0; j--) { StringBuilder line new StringBuilder(); for (int i 0; i n; i) { if (i 0) line.append( ); line.append(a[i][j]); } System.out.println(line); } } }参数说明n是原矩阵行数m是原矩阵列数旋转后输出m行、每行n个数。时间复杂度O(nm)空间复杂度O(nm)存原矩阵。这里不需要真的建一个新矩阵直接按输出顺序访问原矩阵即可。若题目要求顺时针旋转输出顺序会变成从原矩阵第一列开始、每列从下到上不要混。Z 字形扫描的难点在方向控制。把矩阵坐标的i j看作斜线编号从 0 到2n - 2依次输出。样例中i j 0是(0,0)i j 1是(0,1)、(1,0)i j 2是(2,0)、(1,1)、(0,2)。可以看出偶数斜线从下往上走奇数斜线从上往下走。写循环时先算这条斜线的行起点和行终点偶数斜线行从min(s, n - 1)递减到max(0, s - (n - 1))奇数斜线反过来。列坐标用j s - i直接算不需要额外判断边界。这个题的数据范围n ≤ 500输出n * n个数用StringBuilder拼一行可以减少输出次数。4. 排序与图论数字排序、便利城市对、网络延时的模型转换这一章的三道题分别代表三种模型统计后排序、有向图强连通分量、树的直径。它们比基础模拟多了一层“把题面翻译成图或排序规则”的工作。数字排序的坑在双关键字便利城市对坑在“有向可达”和“无向连通”的区别网络延时的坑在“最多步数”其实是树的直径。下面每道题先讲模型再给可复现的代码骨架最后说清楚参数和边界。4.1 数字排序桶计数后双关键字排序题面要求统计每个整数出现次数按出现次数从多到少输出次数相同则先输出值较小的。输入范围1 ≤ n ≤ 1000给出的数不超过 1000所以可以直接开一个长度 1001 的计数数组。统计完之后把所有出现过的数放进列表按“次数降序、值升序”排序。这里不要用TreeMap直接按 key 排序因为题目第一关键字是次数不是数值。排序比较器写成x[1] ! y[1] ? y[1] - x[1] : x[0] - y[0]前一半是次数降序后一半是值升序。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cnt new int[1001]; for (int i 0; i n; i) { cnt[sc.nextInt()]; } Listint[] list new ArrayList(); for (int v 0; v 1000; v) { if (cnt[v] 0) { list.add(new int[]{v, cnt[v]}); // [数值, 出现次数] } } list.sort((x, y) - x[1] ! y[1] ? y[1] - x[1] : x[0] - y[0]); StringBuilder out new StringBuilder(); for (int[] p : list) { out.append(p[0]).append( ).append(p[1]).append(\n); } System.out.print(out); } }参数说明cnt[v]存数值v的出现次数列表元素是长度为 2 的数组。时间复杂度是O(n 1000 log 1000)空间复杂度是O(1000)。易错点有两个一是次数相同的时候忘了按值升序二是把输出写成了“数值 次数”以外的顺序。题目要求每行两个整数分别表示一个给定整数和它出现的次数按次数递减输出。样例中3出现 4 次、2出现 3 次、5出现 3 次2和5次数相同所以先输出2再输出5。4.2 便利城市对强连通分量缩点后算组合数便利城市对的定义是城市 A 能到城市 B城市 B 也能到城市 A。翻译成图论就是“两个城市在同一个强连通分量里”。注意这是有向图不能拿并查集把边当成无向边来合并。样例中2 - 3 - 4 - 2形成一个环{2,3,4}两两互为便利城市对贡献是3 * 2 / 2 3对(2,3)和(3,2)算同一对所以每个大小为s的强连通分量贡献s * (s - 1) / 2对。数据范围n ≤ 10000、m ≤ 100000需要用邻接表计数用long。import java.util.*; public class Main { static ListInteger[] g; static int[] dfn, low, stack; static boolean[] inStack; static int timer, top; static long pairs; static void tarjan(int u) { dfn[u] low[u] timer; stack[top] u; inStack[u] true; for (int v : g[u]) { if (dfn[v] 0) { tarjan(v); low[u] Math.min(low[u], low[v]); } else if (inStack[v]) { low[u] Math.min(low[u], dfn[v]); } } if (low[u] dfn[u]) { int v, size 0; do { v stack[top--]; inStack[v] false; size; } while (v ! u); pairs (long) size * (size - 1) / 2; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); g new ArrayList[n 1]; for (int i 1; i n; i) g[i] new ArrayList(); for (int i 0; i m; i) { int a sc.nextInt(); int b sc.nextInt(); g[a].add(b); // 有向边不能反着加 } dfn new int[n 1]; low new int[n 1]; stack new int[n 1]; inStack new boolean[n 1]; for (int i 1; i n; i) { if (dfn[i] 0) tarjan(i); } System.out.println(pairs); } }参数说明dfn[u]是时间戳low[u]是能回溯到的最早时间戳stack存当前强连通分量的候选点inStack用来判断点是否在栈里。每个强连通分量弹栈时统计大小size累加无序对。时间复杂度O(n m)空间复杂度O(n m)。注意pairs用long因为n 10000时一个分量最多贡献约五千万对虽然int勉强能放但中间乘法size * (size - 1)可能溢出先转long更稳。另外递归深度最坏可到n如果提交环境栈较小可以把 Tarjan 改成显式栈的迭代写法。4.3 网络延时树的直径两次 BFS网络延时题给出一棵层级结构的交换机和终端电脑问任意两个设备之间传递消息最多需要多少步。所有交换机按层级连接终端电脑直接连交换机整张图是一棵树。树上任意两点最远距离就是树的直径。求直径的标准做法是从任意点出发 BFS 找到最远点a再从a出发 BFS 找到最远点ba到b的距离就是直径。不要只从根节点 BFS 一次然后取最大深度那样得到的只是树高不是直径。p a hrefhttps://download.csdn.net/download/Alonei6/89062246 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p 
长河君 · 2026/10/31 18:56:39 · 阅读 1.2k CSP认证历年真题刷题指南：基础模拟、日期矩阵与图论模型
简介这份CCF-CSP认证考试历年真题面向准备参加CCF计算机软件能力认证的在校学生、算法学习者与竞赛入门选手核心用途是借助原题文本熟悉认证考试的题型结构、难度梯度与提交规范。压缩包共1个PDF文件大小约1.99MB集中收录历年试题的完整题面包括问题描述、输入输出格式、样例说明、评测用例规模与约定等便于按年份和试题编号检索练习。需要说明的是文件中不含参考答案更适合用作自测与模拟训练材料。借助这些原题读者可以还原真实考试场景训练数列分段、日期计算、模板生成、图论计数等常见题型的建模与编码思路也能对照时间与内存限制检查程序效率。目前已有7998人学习适合作为备考阶段的基础题库与查漏补缺资料。1. CSP 认证历年真题怎么刷从“会写”到“能过评测”的三道门槛CSP 认证考试历年真题里最容易被低估的不是最后一道压轴题而是第一题旁边的“提交确认”。很多人平时刷题能写出思路一到评测就翻车主类名不是Main、程序里多了一句“请输入 n”、结果中间顺手打印了调试数组最后全部判错。这场考试真正考的是三件事能不能把题意翻译成稳定代码能不能在 1.0s 和 256MB 的限制里选对数据结构能不能严格遵守标准输入输出。这套 2014、2015 年的真题合集只有题面、不含答案正好逼你把每道题的判定依据写出来而不是看完题解就产生“我会了”的错觉。适合正在准备认证考试的人也适合拿它练校招笔试基础题的人。先别急着攻图论和动态规划把数列分段、门禁系统、日期计算、图像旋转这几类题刷到一次提交就过后面的分数才有意义。2. 基础模拟数列分段、门禁系统、模板生成的三类送分骨架基础题的分值不是“白送”而是用来筛掉读题不细、输出格式不稳的人。这一章挑三道很典型的题一道只看相邻元素一道考计数数组一道考字符串的一次替换。它们看起来不像同一个模块但答题骨架一致先把输入范围看清楚再决定用数组还是映射最后只输出题目要求的那个结果。下面每道题都给一段可提交风格的 Java 代码重点看注释和参数范围不要只背循环。2.1 数列分段相邻不同才切一刀题面说“连续相同的最长整数序列算成一段”这句话已经把算法说完了只需要比较当前数和前一个数不同就段数加一。样例里8 8 8 0 12 12 8 0的答案是 5不是 4因为最后的8和前面的8中间隔了0和12不能合并。很多人第一反应是统计不同数字的个数样例一跑就发现对不上。这个题的数据范围是1 ≤ n ≤ 10000 ≤ ai ≤ 1000用Scanner足够不需要建哈希表。注意n 1时答案应为 1循环不能从 0 开始又把第一项算一次。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int prev sc.nextInt(); // 第一项先读进来作为当前段的基准 int segments 1; // n 1至少有一段 for (int i 1; i n; i) { int cur sc.nextInt(); if (cur ! prev) { // 只和相邻项比较不是和前面所有项比较 segments; prev cur; // 新段从当前数开始 } } System.out.println(segments); } }这段代码里prev承担的是“当前段最后一个值”的角色。如果cur prev说明还在同一段里什么都不做如果不等说明段断了计数器加一同时把基准换成cur。时间复杂度是O(n)空间复杂度是O(1)。易错点有两个一是把“连续相同”理解成“整个数组里相同值只算一次”二是忘了n 1的初始值。评测时只输出一个整数不要打印“段数是”这种提示语。2.2 门禁系统计数数组比 Map 更稳这道题问每条记录中的读者编号是第几次出现。输入保证读者编号是不超过n的正整数这就给了很明确的信号可以直接开一个长度为n 1的计数数组。每读到一个编号id就执行cnt[id]然后输出cnt[id]。如果编号范围没有这么规整才需要考虑HashMap。基础题里能开数组就开数组数组的常数小、不会因为哈希冲突或装箱拖慢速度。输出要求是一行n个整数用空格分隔最后一个数后面不要多打一个空格更稳妥。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cnt new int[n 1]; // 题目保证读者编号不超过 n StringBuilder out new StringBuilder(); for (int i 0; i n; i) { int id sc.nextInt(); cnt[id]; // 当前编号出现次数加一 if (i 0) out.append( ); out.append(cnt[id]); // 输出的是“第几次出现” } System.out.println(out); } }参数含义很直接n是记录条数cnt[id]是编号id到目前为止出现的次数。用StringBuilder是为了避免在循环里反复拼接字符串。这里有一个小检查如果题目没有保证编号不超过n这段代码会数组越界那时才改成MapInteger, Integer。考试时先看“评测用例规模与约定”这句话比题面故事更有用。输出时不要输出每条记录的原始编号题目要的是出现次数。2.3 模板生成系统一次替换不递归模板生成系统考的是字符串处理但真正容易错的是替换规则。变量名由大小写字母、数字和下划线构成第一个字符不能是数字长度不超过 16变量名区分大小写标记里的变量未定义时替换成空串模板不递归生成也就是说变量的值里如果又出现{{ VAR }}不能再替换。最后这一条决定了不能用“按变量逐个replace”的写法因为前一次替换插入的值可能被后一次替换误伤。更稳的做法是用正则一次扫描模板行遇到标记就查映射表没查到就写空串。import java.util.*; import java.util.regex.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int m sc.nextInt(); // 模板行数 int n sc.nextInt(); // 变量个数 sc.nextLine(); String[] tpl new String[m]; for (int i 0; i m; i) { tpl[i] sc.nextLine(); } MapString, String vars new HashMap(); for (int i 0; i n; i) { String line sc.nextLine(); int sp line.indexOf( ); String key line.substring(0, sp); // 值用双引号包住去掉首尾两个引号值内部可能含空格 String val line.substring(sp 2, line.length() - 1); vars.put(key, val); } // 变量名首字符不能是数字总长度不超过 16 Pattern p Pattern.compile(\\{\\{\\s*([A-Za-z_][A-Za-z0-9_]{0,15})\\s*\\}\\}); for (String line : tpl) { Matcher mat p.matcher(line); StringBuffer sb new StringBuffer(); while (mat.find()) { String key mat.group(1); String val vars.getOrDefault(key, ); // 未定义变量替换为空串 // 变量值里可能有 $ 或 \必须 quoteReplacement mat.appendReplacement(sb, Matcher.quoteReplacement(val)); } mat.appendTail(sb); System.out.println(sb.toString()); } } }这段代码的关键参数是正则里的\\s*和{0,15}。\\s*允许{{ name }}这种花括号和变量名之间有空格的形式{0,15}表示变量名首字符之外最多再跟 15 个字符总长度不超过 16。Matcher.quoteReplacement不能省因为变量的值可以是除双引号外的任意可打印 ASCII 字符其中可能包含$和反斜杠直接拼进替换串会被正则当成特殊符号。还一个细节题目说模板不递归所以一次find扫描只处理模板原文里的标记插入的值不再进入下一轮匹配。若变量未定义getOrDefault返回空串相当于把标记删除。输出时每一行模板都要输出哪怕这一行没有变量。3. 日期与矩阵闰年、星期推算、旋转和 Z 字形扫描的硬骨头日期题和矩阵题在真题里出现得很稳定因为它们不依赖复杂算法却能同时考边界、下标和格式。日期题的核心不是写一堆if而是把闰年规则、月份天数、星期起点拆成可复用的函数矩阵题的核心不是背旋转公式而是先写出“新矩阵的第i行第j列对应原矩阵的哪个位置”。这一章用日期计算、节日推算、图像旋转和 Z 字形扫描四个点把这类题的答题顺序固定下来先定基准再推公式最后校验下标范围。3.1 日期计算月份前缀表比一堆 if 稳题面给年份y和整数d问这一年的第d天是几月几日。闰年规则写得很清楚年份是 400 的整数倍或者年份是 4 的整数倍且不是 100 的整数倍。注意1900不是闰年2000是闰年这两个年份经常被拿来当边界。实现时先建一个平年月份天数数组判断闰年后把二月改成 29然后让d依次减去每个月的天数直到d小于等于当前月天数。输出两行第一行月份第二行日期。import java.util.Scanner; public class Main { static boolean isLeap(int y) { return y % 400 0 || (y % 4 0 y % 100 ! 0); } public static void main(String[] args) { Scanner sc new Scanner(System.in); int y sc.nextInt(); int d sc.nextInt(); int[] days {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) days[1] 29; // 闰年二月 29 天 int mon 0; // 数组下标最后输出 mon 1 while (d days[mon]) { d - days[mon]; mon; } System.out.println(mon 1); System.out.println(d); } }参数说明y的范围是 1900 到 2015d的范围是 1 到 365。mon从 0 开始因为数组下标从 0 开始输出月份时要加一。d在循环里被不断减去整月天数剩下的就是当月第几天。这段代码的时间复杂度是O(12)可以忽略。易错点是闰年判断写成y % 4 0就结束导致 1900 年被当成闰年另一个是输出格式题目要求两行两个整数不要输出成3/21这种形式。3.2 节日先算月首星期再推第 b 个星期 c节日题给a, b, c, y1, y2要求输出每年a月的第b个星期c的日期不存在就输出none。题面还给了一个重要基准1850 年 1 月 1 日是星期二。这类题不要一上来就写循环翻日历先算目标年份a月 1 日是星期几再算第一个星期c出现在几号。设c用 1 到 7 表示星期一到星期日月首星期为w那么第一个星期c的日期是1 (c - w 7) % 7第b个就是在这个基础上加(b - 1) * 7。如果结果超过当月天数输出none。static int weekdayOfFirstDay(int y, int a) { // 返回 1周一 ... 7周日 int days 0; for (int year 1850; year y; year) { days isLeap(year) ? 366 : 365; } int[] mon {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (isLeap(y)) mon[1] 29; for (int i 0; i a - 1; i) { days mon[i]; } // 1850-01-01 是星期二所以先加 1 再取模最后加 1 映射到 1..7 return ((days 1) % 7) 1; }这段函数只算月首星期后面的日期推算放在主流程里。days表示从 1850 年 1 月 1 日到目标年a月 1 日前一天的总天数。公式((days 1) % 7) 1的推导可以用一个点校验days 0时返回 2正好是星期二。得到月首星期w后第一个星期c的日期为1 (c - w 7) % 7。如果这个日期大于当月天数说明这个月没有第b个星期c。输出格式要求四位年份、两位月份、两位日期中间用斜杠分隔位数不足前补零。可以用String.format(%04d/%02d/%02d, y, a, day)不要手动拼字符串漏零。3.3 图像旋转与 Z 字形扫描先定坐标再写循环图像旋转题要求把一个n行m列的矩阵逆时针旋转 90 度。直接背“新矩阵第 i 行第 j 列等于原矩阵第 j 列第 n-1-i 行”容易绕晕更稳的写法是看输出顺序逆时针旋转后共有m行每一行对应原矩阵的一列而且是从最后一列开始列内从上到下。所以外层循环让原列j从m - 1到 0内层循环让原行i从 0 到n - 1依次输出a[i][j]。样例2 3的矩阵旋转后输出3 4 / 5 2 / 1 3用这个顺序一对就明白。import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); int[][] a new int[n][m]; for (int i 0; i n; i) { for (int j 0; j m; j) { a[i][j] sc.nextInt(); } } // 逆时针 90 度按原矩阵的列从右到左输出每列从上到下 for (int j m - 1; j 0; j--) { StringBuilder line new StringBuilder(); for (int i 0; i n; i) { if (i 0) line.append( ); line.append(a[i][j]); } System.out.println(line); } } }参数说明n是原矩阵行数m是原矩阵列数旋转后输出m行、每行n个数。时间复杂度O(nm)空间复杂度O(nm)存原矩阵。这里不需要真的建一个新矩阵直接按输出顺序访问原矩阵即可。若题目要求顺时针旋转输出顺序会变成从原矩阵第一列开始、每列从下到上不要混。Z 字形扫描的难点在方向控制。把矩阵坐标的i j看作斜线编号从 0 到2n - 2依次输出。样例中i j 0是(0,0)i j 1是(0,1)、(1,0)i j 2是(2,0)、(1,1)、(0,2)。可以看出偶数斜线从下往上走奇数斜线从上往下走。写循环时先算这条斜线的行起点和行终点偶数斜线行从min(s, n - 1)递减到max(0, s - (n - 1))奇数斜线反过来。列坐标用j s - i直接算不需要额外判断边界。这个题的数据范围n ≤ 500输出n * n个数用StringBuilder拼一行可以减少输出次数。4. 排序与图论数字排序、便利城市对、网络延时的模型转换这一章的三道题分别代表三种模型统计后排序、有向图强连通分量、树的直径。它们比基础模拟多了一层“把题面翻译成图或排序规则”的工作。数字排序的坑在双关键字便利城市对坑在“有向可达”和“无向连通”的区别网络延时的坑在“最多步数”其实是树的直径。下面每道题先讲模型再给可复现的代码骨架最后说清楚参数和边界。4.1 数字排序桶计数后双关键字排序题面要求统计每个整数出现次数按出现次数从多到少输出次数相同则先输出值较小的。输入范围1 ≤ n ≤ 1000给出的数不超过 1000所以可以直接开一个长度 1001 的计数数组。统计完之后把所有出现过的数放进列表按“次数降序、值升序”排序。这里不要用TreeMap直接按 key 排序因为题目第一关键字是次数不是数值。排序比较器写成x[1] ! y[1] ? y[1] - x[1] : x[0] - y[0]前一半是次数降序后一半是值升序。import java.util.*; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int[] cnt new int[1001]; for (int i 0; i n; i) { cnt[sc.nextInt()]; } Listint[] list new ArrayList(); for (int v 0; v 1000; v) { if (cnt[v] 0) { list.add(new int[]{v, cnt[v]}); // [数值, 出现次数] } } list.sort((x, y) - x[1] ! y[1] ? y[1] - x[1] : x[0] - y[0]); StringBuilder out new StringBuilder(); for (int[] p : list) { out.append(p[0]).append( ).append(p[1]).append(\n); } System.out.print(out); } }参数说明cnt[v]存数值v的出现次数列表元素是长度为 2 的数组。时间复杂度是O(n 1000 log 1000)空间复杂度是O(1000)。易错点有两个一是次数相同的时候忘了按值升序二是把输出写成了“数值 次数”以外的顺序。题目要求每行两个整数分别表示一个给定整数和它出现的次数按次数递减输出。样例中3出现 4 次、2出现 3 次、5出现 3 次2和5次数相同所以先输出2再输出5。4.2 便利城市对强连通分量缩点后算组合数便利城市对的定义是城市 A 能到城市 B城市 B 也能到城市 A。翻译成图论就是“两个城市在同一个强连通分量里”。注意这是有向图不能拿并查集把边当成无向边来合并。样例中2 - 3 - 4 - 2形成一个环{2,3,4}两两互为便利城市对贡献是3 * 2 / 2 3对(2,3)和(3,2)算同一对所以每个大小为s的强连通分量贡献s * (s - 1) / 2对。数据范围n ≤ 10000、m ≤ 100000需要用邻接表计数用long。import java.util.*; public class Main { static ListInteger[] g; static int[] dfn, low, stack; static boolean[] inStack; static int timer, top; static long pairs; static void tarjan(int u) { dfn[u] low[u] timer; stack[top] u; inStack[u] true; for (int v : g[u]) { if (dfn[v] 0) { tarjan(v); low[u] Math.min(low[u], low[v]); } else if (inStack[v]) { low[u] Math.min(low[u], dfn[v]); } } if (low[u] dfn[u]) { int v, size 0; do { v stack[top--]; inStack[v] false; size; } while (v ! u); pairs (long) size * (size - 1) / 2; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); int m sc.nextInt(); g new ArrayList[n 1]; for (int i 1; i n; i) g[i] new ArrayList(); for (int i 0; i m; i) { int a sc.nextInt(); int b sc.nextInt(); g[a].add(b); // 有向边不能反着加 } dfn new int[n 1]; low new int[n 1]; stack new int[n 1]; inStack new boolean[n 1]; for (int i 1; i n; i) { if (dfn[i] 0) tarjan(i); } System.out.println(pairs); } }参数说明dfn[u]是时间戳low[u]是能回溯到的最早时间戳stack存当前强连通分量的候选点inStack用来判断点是否在栈里。每个强连通分量弹栈时统计大小size累加无序对。时间复杂度O(n m)空间复杂度O(n m)。注意pairs用long因为n 10000时一个分量最多贡献约五千万对虽然int勉强能放但中间乘法size * (size - 1)可能溢出先转long更稳。另外递归深度最坏可到n如果提交环境栈较小可以把 Tarjan 改成显式栈的迭代写法。4.3 网络延时树的直径两次 BFS网络延时题给出一棵层级结构的交换机和终端电脑问任意两个设备之间传递消息最多需要多少步。所有交换机按层级连接终端电脑直接连交换机整张图是一棵树。树上任意两点最远距离就是树的直径。求直径的标准做法是从任意点出发 BFS 找到最远点a再从a出发 BFS 找到最远点ba到b的距离就是直径。不要只从根节点 BFS 一次然后取最大深度那样得到的只是树高不是直径。p a hrefhttps://download.csdn.net/download/Alonei6/89062246 stylecolor:#ec7500;font-size:14px; 本文还有配套的精品资源点击获取 /a img altmenu-r.4af5f7ec.gif srchttps://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif stylewidth:16px;margin-left:4px;vertical-align:text-bottom;cursor:text; /p