简介面向团体程序设计天梯赛CCCC备赛选手的真题解析PDF覆盖近三年L2、L3梯级题目适合已有基础、希望冲击进阶分与登顶分的高校学生及竞赛教练。这份文档将梯赛高频题型分类整理每个题目都给出题意分析、完整可运行的C代码以及关键算法思路注释并针对链表、二叉树、并查集、最短路径等核心考点做要点提示。与基础级L1题目不同L2/L3更强调在限定时间内综合运用数据结构与算法解决实际问题通过近三年真题的集中拆解可以快速感受命题风格、难度曲线和常见陷阱避免赛场上无从下手。包体为单个PDF文件大小仅2.53MB方便离线阅读与打印。目前已有974人学习浏览适合赛前一个月用于专题强化、模拟自测及错误复盘也可作为教学培训的辅助材料。1. 团体程序设计天梯赛真题解析这份代码包到底在帮你练什么团体程序设计天梯赛的 L2、L3 真题在 PTA 平台上属于那种“看着有思路、一交就翻车”的题。上个月帮学弟调一套近三年的 L2 真题他挂在链表反转上两个晚上本地样例全过提交全是段错误。这类题不像 L1 考单点知识而是把输入解析、边界处理、数据结构串在一起考代码解析的价值恰恰在于把完整解法和卡住的地方同时摆出来。这份真题及代码解析适合正在备赛的本科生、想快速过一轮题型的研究生还有需要真实教学案例的带队老师。里面的 L1 部分代码质量参差但正是这种参差能看出不同写法的差距值得一份份改过来。2. 从 L1 热身题看代码基本功沙漏公式、字符处理与分数求和2.1 打印沙漏2×row×(row2)1 是怎么推出来的打印沙漏是 L1 里经典图形题也是后面 L2 图形模拟题的起点。很多人卡在这题不是因为不会写循环而是算不准“给定 N 个符号最多能组成多大的沙漏”。解析代码里用了一个公式2 * i * (i 2) 1第一眼看有点懵拆开推导就清楚了。如果定义 row 为沙漏中心线以上或以下的行数那么每半边符号总数是sum(2*i1)i 从 1 到 row结果等于row * (row 2)。左右两半加上中心 1 个符号总符号数就是2 * row * (row 2) 1。代码里那个判断循环本质上是在从小到大试算“半边高度为 i 时需要多少符号”第一次超过 N 就说明 i 大了回退一行。#include iostream using namespace std; int main() { int N, row 0; char c; cin N c; for (int i 0; i N; i) { if ((2 * i * (i 2) 1) N) { // 总符号数超过 N回退一行 row i - 1; break; } } // 上半部分符号数从 2*row1 递减到 3 for (int i row; i 1; i--) { for (int k row - i; k 1; k--) cout ; for (int j i * 2 1; j 1; j--) cout c; cout endl; } // 中心单独一个符号 for (int i 0; i row; i) cout ; cout c endl; // 下半部分符号数从 3 递增回 2*row1 for (int i 1; i row; i) { for (int k row - i; k 1; k--) cout ; for (int j i * 2 1; j 1; j--) cout c; cout endl; } cout (N - (2 * row * (row 2) 1)); // 输出剩余符号数 return 0; }这段代码的逻辑分三段先算 row再分别打印上半、中心和下半。参数上row 表示半边行数而不是最大行的符号数很多人把 row 当成“最大行符号数”去套公式结果怎么都对不上。比如 N19row2总符号数2 * 2 * 4 1 17剩余 2和样例一致。用公式时注意 N 的范围只有 1000直接循环试算是没问题的不需要去解二次方程考场上一旦解错反而耽误时间。2.2 个位数统计与 A-B字符串处理的两个典型姿势个位数统计这道题看起来是数学题实际考的是大数输入。N 是不超过 1000 位的正整数int 和 long long 全都装不下标准做法是当字符串读。解析代码用s[i] - 0把字符转成数字再拿这个数字当数组下标做计数这其实就是最简单的哈希。#include iostream #include string using namespace std; int main() { string s; cin s; int len s.length(); int a[10] {0}; // 下标 0~9 对应十个数字 for (int i 0; i len; i) a[s[i] - 0]; for (int i 0; i 10; i) { if (a[i] ! 0) cout i : a[i] endl; } return 0; }这里有两个习惯值得保持数组必须初始化成 0否则本地可能碰巧是 0交到评测机上就是随机值输出顺序直接按 i 从 0 到 9 走天然满足“按 D 升序”不用额外排序。字符偏移s[i] - 0是竞赛常用手法后面处理身份证、数字字符串都会反复用到。A-B 则是另一个典型从字符串 A 中删掉所有出现在 B 里的字符。这份解析用了一个 book 数组标记 256 个 ASCII 码思路是把“判断字符是否存在”的复杂度从 O(lenA × lenB) 降到 O(lenA lenB)。注意题目说字符串由可见 ASCII 码和空白字符组成所以 B 里的空格也是要删的字符必须用 getline 读整行不能用 cin 代替否则空格后全被截断样例都过不了。#include iostream using namespace std; int book[256]; // 标记 ASCII 码初始为 0 int main() { string s, a; getline(cin, s); // 读整行保留空格 getline(cin, a); for (int i 0; i a.length(); i) book[a[i]] 1; for (int i 0; i s.length(); i) { if (book[s[i]] 1) continue; cout s[i]; } return 0; }book 数组大小取 256因为字符作为下标时会被转成 ASCII 码落在 0 到 255 之间。这个技巧能解决一大类“集合判定”问题L2 里不少字符串模拟题都会用到同款思路。如果字符集扩大到 Unicode数组就不合适了该换 unordered_set 就换别硬扛。2.3 分数求和每一步都约分别把溢出留给最后N 个数求和是 L1 里最值得反复做的一道题因为它把“类型溢出”和“约分时机”两个问题一次性暴露出来。解析里原话提到“浮点错误”其实那根本不是浮点而是分母变成 0 或取模 0 时报的错。罪魁祸首是累加过程中分子分母一路膨胀long long 都扛不住。正确的做法是每累加一个新分数之前先对已有的和约分再对新分数约分最后才做通分相加。这样每一步的数值都被压住不会等到最后一次性爆掉。#include cstdio #include cstdlib using namespace std; long long gcd(long long a, long long b) { return b 0 ? a : gcd(b, a % b); } int main() { long long n, a, b, suma 0, sumb 1, gcdvalue; scanf(%lld, n); for (int i 0; i n; i) { scanf(%lld/%lld, a, b); // 先约分已有的和 gcdvalue (suma 0 || sumb 0) ? 1 : gcd(abs(suma), abs(sumb)); sumb sumb / gcdvalue; suma suma / gcdvalue; // 再约分当前输入的分数 gcdvalue (a 0 || b 0) ? 1 : gcd(abs(a), abs(b)); a a / gcdvalue; b b / gcdvalue; // 通分相加 suma a * sumb suma * b; sumb b * sumb; } long long integer suma / sumb; suma suma - (sumb * integer); gcdvalue (suma 0 || sumb 0) ? 1 : gcd(abs(suma), abs(sumb)); suma suma / gcdvalue; sumb sumb / gcdvalue; if (integer ! 0) { printf(%lld, integer); if (suma ! 0) printf( ); } if (suma ! 0) printf(%lld/%lld, suma, sumb); if (integer 0 suma 0) printf(0); return 0; }这段代码的 gcd 是递归写法参数里出现 0 时直接返回 1避免取模 0。通分公式suma a * sumb suma * b把新分数交叉相乘累加注意这里的 a、b 都已经约过分。最后输出分了三段处理整数部分、分数部分、以及“结果为 0”的情况。这道题在 PAT 上有一个测试点专门卡 long long 溢出凡是最后才约分的写法基本都会挂在这个点上。3. L2 常考题型拆解链表、二叉树与模拟题的通用模板3.1 链表操作题用数组模拟别开结构体指针天梯赛 L2 的链表题有个共同特点输入给的是结点的五位整数地址而不是像教科书那样的直接构造好的链表。比如“反转链表”“重排链表”这类题直接用 struct 加指针去建链很容易在悬空指针上翻车而且地址范围是 1e5 级别开结构体数组按地址索引反而更稳。常见的做法是开两个数组data[addr]存结点的值nxt[addr]存下一个结点的地址。反转时不需要真的动内存只需要改nxt的指向最后按新顺序输出即可。// 数组模拟链表地址范围 0~100000直接用下标访问 int data[100005], nxt[100005]; // 反转以 head 开头的链表返回新的头地址 int reverseList(int head) { int prev -1, cur head; while (cur ! -1) { int n nxt[cur]; // 先记录后继否则断链后找不到 nxt[cur] prev; prev cur; cur n; } return prev; }注意循环终止条件是cur -1因为题目约定 -1 表示链表结束。反转过程是经典的三指针滑动prev、cur、n 各司其职关键就是n nxt[cur]必须在修改nxt[cur]之前执行否则当前结点的后继信息就丢了。很多段错误都是这个顺序写反导致的。重排链表这类变形题思路是先用快慢指针找到中点把链表切成两半再交替合并。用数组模拟时“快慢指针”就变成两个整数下标在数组里走逻辑比指针版更直观。我在实际写这类题时一般还会多开一个valid数组标记某地址是否真的出现在链表中因为输入里经常混着多余结点不筛掉的话输出会对不上。这个“多余结点”的坑就是学弟两个晚上没调出来的原因。3.2 二叉树题递归遍历与最近公共祖先的朴素做法L2 的二叉树题不像 L3 那么深多数落在“建树 遍历 求某个信息”的组合上。比如给中序和后序让重建二叉树或者给一棵树求某种路径。这类题最稳的做法是递归关键是确定递归函数的返回值代表什么以及空子树怎么处理。以最近公共祖先为例如果题目没有要求复杂度朴素做法就够用分别收集根到两个目标结点的路径再从前往后比最后一个相同的结点就是 LCA。这个办法好处是思路直白不容易写错。#include vector using namespace std; struct TreeNode { int val; TreeNode *left, *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; // 收集从根到 target 的路径成功返回 true bool dfs(TreeNode* root, int target, vectorint path) { if (root nullptr) return false; path.push_back(root-val); if (root-val target) return true; if (dfs(root-left, target, path)) return true; if (dfs(root-right, target, path)) return true; path.pop_back(); // 回溯撤销当前结点 return false; } // 求 u 和 v 的 LCA int lca(TreeNode* root, int u, int v) { vectorint pathU, pathV; dfs(root, u, pathU); dfs(root, v, pathV); int ans -1; int len min(pathU.size(), pathV.size()); for (int i 0; i len; i) { if (pathU[i] pathV[i]) ans pathU[i]; else break; } return ans; }这个模板里最关键的是 dfs 后的path.pop_back()。如果把回溯忘了路径里会混进不该有的结点LCA 结果直接错。至于复杂度每次查询都是 O(N)N 是结点数L2 的数据量一般能过。要是 L3 遇到多组查询就得换倍增或 Tarjan 离线做法但那是另一套模板了。这里的参数 root 传 nullptr 时必须返回 false否则访问空指针就是段错误。3.3 模拟题的分寸结构化数据 一次排序解决名次并列L2 里有一类题目本身不考复杂算法考的是“能不能把题目规则看懂并实现出来”典型代表是排行榜名次、功夫传人这类模拟题。这类题最容易挂的地方不是算法而是名次并列的处理。题目常见说法是“输出前 K 名”但名额往往包含并列。也就是说如果第 K 名和第 K1 名分数相同两个都要输出。用for (int i 0; i k; i)直接截断必然漏掉并列的人。#include algorithm #include iostream #include string #include vector using namespace std; struct Stu { string name; int score; }; bool cmp(const Stu a, const Stu b) { if (a.score ! b.score) return a.score b.score; // 分数降序 return a.name b.name; // 姓名升序 } int main() { int n, k; cin n k; vectorStu stu(n); for (int i 0; i n; i) cin stu[i].name stu[i].score; sort(stu.begin(), stu.end(), cmp); int rank 1; for (int i 0; i n; i) { if (i 0 stu[i].score ! stu[i - 1].score) rank i 1; if (rank k) break; // 只输出前 k 名但包含了并列 cout rank stu[i].name stu[i].score \n; } return 0; }这里 rank 的更新逻辑是精髓分数和上一个人相同rank 不变分数变了rank 直接跳到当前下标加一。if (rank k) break保证了并列第 K 名的人不会漏掉也不会多输出后面的人。排序那块我一般会补一个姓名升序的二级排序条件因为题目常常有这个要求没写的话测试点会挂在同分不同名的顺序上。模拟题的分寸在于数据能存进结构体就别拆成散变量能一次排序解决就别手写名次逻辑。4. L3 难点怎么破动态规划与图论题的入手顺序4.1 动态规划先写暴力递归再改记忆化L3 的动态规划题第一眼往往吓人但绝大多数都能从暴力递归起步。我的习惯是先不管复杂度把状态定义写清楚用递归实现转移然后加一个 memo 数组判重能过的题直接过不能过的再改迭代写法。这个顺序能避免一上来就纠结 dp 数组的维度顺序。以 0-1 背包为例这是 L3 里出现频率很高的模型也是后面很多变形题的底子。#include iostream #include vector using namespace std; int main() { int n, W; cin n W; vectorint w(n), v(n); for (int i 0; i n; i) cin w[i] v[i]; // dp[j] 表示容量为 j 的背包能装下的最大价值 vectorint dp(W 1, 0); for (int i 0; i n; i) { // 逆序遍历容量保证每个物品只选一次 for (int j W; j w[i]; j--) { dp[j] max(dp[j], dp[j - w[i]] v[i]); } } cout dp[W] endl; return 0; }注意内层循环必须从 W 往 w[i] 倒着走。如果正着走dp[j - w[i]] 可能已经包含了当前物品等于允许一个物品选多次那就变成完全背包了。这个差别是 L3 常挖的坑换一下遍历方向就是另一种题。状态转移dp[j] max(dp[j], dp[j - w[i]] v[i])的语义是“不选当前物品”和“选当前物品”两种决策取较大值。如果递归写法状态就是f(i, j)表示前 i 个物品在容量 j 下的最大价值转移同样分选与不选。记忆化版本只是把f(i, j)存进二维数组遇到重复状态直接返回。两种写法等价但考场上一旦确认状态和转移对了迭代版写起来更快出 bug 的概率也低一些。4.2 图论模板堆优化 Dijkstra 与拓扑排序判环L3 的最短路题基本不会出裸的弗洛伊德数据范围稍微大一点就得用堆优化的 Dijkstra。模板本身不复杂容易错的是堆里的“过期元素”没跳过或者松弛条件写反。#include iostream #include queue #include vector using namespace std; const int INF 0x3f3f3f3f; void dijkstra(int start, int n, vectorvectorpairint, int adj, vectorint dist) { dist.assign(n, INF); dist[start] 0; // 小顶堆pair 前一个是距离后一个是结点编号 priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; pq.push({0, start}); while (!pq.empty()) { auto [d, u] pq.top(); pq.pop(); if (d ! dist[u]) continue; // 过期元素直接跳过 for (auto [v, w] : adj[u]) { if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.push({dist[v], v}); } } } }if (d ! dist[u]) continue这一行是关键它处理的是同一个结点被多次入堆的情况。没有这行更新过的旧值也会被当成有效状态参与松弛答案可能没错但白白多跑很多次数据一大就超时。邻接表存的是{目标点, 边权}的 pair这是最常用的建图方式。INF 取0x3f3f3f3f在竞赛里很常见因为它足够大又不会让dist[u] w溢出 int。拓扑排序在 L3 里通常是作为前置步骤出现的比如判断有向图有没有环或者给任务排执行顺序。#include iostream #include queue #include vector using namespace std; // 返回拓扑序列如果序列长度小于 n 说明图里有环 vectorint topoSort(int n, vectorvectorint adj) { vectorint indeg(n, 0); for (int u 0; u n; u) { for (int v : adj[u]) indeg[v]; } queueint q; for (int i 0; i n; i) { if (indeg[i] 0) q.push(i); // 入度为 0 的点先入队 } vectorint order; while (!q.empty()) { int u q.front(); q.pop(); order.push_back(u); for (int v : adj[u]) { indeg[v]--; if (indeg[v] 0) q.push(v); } } return order; }这个模板的判环依据是如果图无环每个结点都会被处理一次order 长度等于 n。要是最后 order 长度小于 n说明有结点永远进不了队那就是环在作怪。入度数组的计算要放在建图完成后统一做不能边建边算否则重复边会干扰结果。4.3 难题的时间分配L1 全拿L2 求稳L3 挑软柿子天梯赛的计分方式决定了策略比单题硬刚更重要。团队赛里 L1 是最容易的分数来源一道都不该丢L2 前几题通常只考一个数据结构模板拿稳L3 题量少分值大但难度陡增我一般建议先扫一遍题目找那道“看着眼熟”的比如明显是裸的最短路或裸的背包题优先处理。大模拟题放在最后。L3 有些题本身不考算法考的是读题和耐心比如复杂的格式化输出加状态记录。这类题如果前面已经写了几道状态疲劳时特别容易把规则看漏翻车成本很高。我见过不少人死磕一道大模拟到最后结果 L1 的简单题反而没时间交。时间分配的底线是保证所有能 AC 的题都留出复查时间哪怕只是重新读一遍输出格式要求。5. PTA 判题避坑与常见问题从段错误到格式错误的五个翻车点5.1 大数用 int 读结果全是负数或乱码现象个位数统计、“到底有多二”这类题本地跑样例是对的提交后结果莫名其妙。原因题目给的整数可能长达几十位甚至 1000 位int 只有 32 位读进来直接溢出。更隐蔽的是 char 类型不够存中文字符或扩展字符导致哈希下标越界。解决看到“不超过 1000 位的正整数”无条件按字符串处理。字符串转数字一律用s[i] - 0不要用atoi(s.c_str())。凡是“位数字”这种描述第一反应就是 string。5.2 长整型累加溢出反而报浮点错误现象N 个数求和这类分数运算题提交时报“浮点错误”仔细看代码里根本没有浮点运算。原因评测系统把除零和取模零都归到浮点错误里。分子分母在累加过程中不断膨胀超出 long long 范围后变成未定义行为最后出现分母为 0 的情况。我在拆这份解析时注意到原代码分析也提到这个问题说明它是高频坑。解决每步累加前先对已有结果和当前分数分别约分把数值压住。通分用的乘法要注意顺序先约分再相乘别反过来。5.3 身份证校验码里的 X 处理不当现象查验身份证的题遇到校验码是 X 的号码总是判断错误或者输出的校验码变成负数。原因X 是字符不是数字直接s[17] - 0得到的是负值和权重算出结果完全对不上。解析代码里专门做了if (s[17] X) a[17] 10;的映射这个分支漏掉就是整道题全挂。解决先把校验码统一映射成整数再参与比较。权重数组{7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2}和映射表{1,0,10,9,8,7,6,5,4,3,2}建议直接抄下来常备考前看一眼比现场推节省时间。5.4 行尾空格与 getline 读入现象A-B 这类题输出多了一个空格或少了一个空格被判格式错误。或者字符串题读取时内容少了一段。原因用cin 读含有空格的字符串会被截断。题目明确写“由可见 ASCII 码和空白字符组成”时空格也是数据的一部分必须用 getline 读整行。输出时行尾多出的空格也是格式错误PAT 对行尾空白比较严格。解决读入用getline(cin, s)输出时先拼到 string 里再整体 cout或者用 flag 控制空格只在非首元素前输出。这个习惯用到 L2 的字符串模拟题里能省很多次提交。5.5 沙漏公式里的 row 含义搞混现象打印沙漏总是多一行或少一行剩余符号数和样例对不上。原因把公式里的 row 理解成最大行符号数实际它表示中心线以上或以下的行数。总符号数是2 * row * (row 2) 1不是2 * row 1相关的表达式。公式记错行数自然错。解决推导一遍再背。半边符号数为row * (row 2)乘以 2 加 1 就是总数。如果 N 很小row 可能为 0输出只有一个中心符号代码里对应循环直接不执行这个是边界情况本地一定要测 N1。6. 三遍刷题法把这套代码解析变成自己的错题回收站拿到代码解析包之后最忌讳的是开着解析看一遍觉得自己会了关上编辑器还是写不出来。我自己的刷法是固定三遍每道题都走完才算数。第一遍不看解析独立做。限时L1 每道 15 分钟L2 每道 30 分钟L3 每道 45 分钟。时间到还没 AC 就停下来把自己写了一半的代码原样存好标上“半成品”。这一遍的目的不是 AC是暴露问题是读题读漏了还是某个数据结构不熟还是纯粹手误。这些问题会在后面变成错题清单里的条目。第二遍对照解析逐行看。重点不是看答案而是找差异。我一般会把解析代码和自己的半成品并排打开逐个勾出三样东西我没想到的边界条件、我写错了的循环顺序、解析里比我简洁的写法。每找出一个就在自己的代码里补一行注释写清楚“错在哪、为什么错”。比如链表反转那题我标注的是“必须先存后继再改指向否则原地断链”。第三遍隔一周重写。要求在 30 分钟内一次 AC不许看任何参考资料。这一遍检验的是肌肉记忆凡是还能卡住的地方就是没真正消化的题回到第二遍重新对照一次。三遍之后把这道题的最终版提交记录留档作为以后复习的素材。然后是错题回收站。我用一个 markdown 文件维护每条记录四列题目编号、错误类型、一句话教训、复习日期。类型分为读题错误、边界错误、算法错误、格式错误。错误类型的统计特别有用连续几次都是边界错误就说明每次写完代码后少了一个“补测边界”的习惯而不是算法不会。这个文件不用长每道题一句话复习时扫一遍能想起当时的翻车场景就够了。从那以后我每次刷题收尾都强制走一遍这三遍流程确认每道题都留下了可检索的教训才碰下一道花的时间反而比从前反复提交试错要少得多。希望帮到你。本文还有配套的精品资源点击获取