浙江大学PAT题集1001-1072刷题指南：从基础语法到动态规划

简介这份资源是浙江大学程序能力测试PATAdvanced级别1001至1072题的完整题目集合面向准备PAT考试、刷题提升算法能力的编程学习者尤其适合需要系统训练数据结构与算法设计的进阶选手。压缩包内共1个doc文档约1.03MB集中收录了从AB Format、多项式加法到Emergency最短路径等经典题目的题干、输入输出规范与样例覆盖基础数学运算、数据表示、图论算法等多个知识模块。已有2850人学习下载说明其在备考群体中具有一定参考价值。通过逐题研读与练习读者可以熟悉PAT的判题格式与时间、内存限制要求掌握Dijkstra、Floyd-Warshall等算法的实际应用场景并借助样例输入输出验证自己的实现思路为冲击高分和更高级别的编程挑战打下扎实基础。1. 从 1001 到 1072这套题单为什么值得你花两个月啃完如果你正在准备算法竞赛、考研机试或者单纯想找一套能覆盖基础语法到中级算法的完整训练集那“浙江大学pat题目集合1001-1072”大概率已经出现在你的收藏夹里了。这套题单覆盖了从输入输出格式训练、字符串处理、模拟题、排序查找到动态规划入门、图论基础等核心考点题号连续、难度梯度清晰非常适合作为系统刷题的第一套主线材料。但很多人翻了几题就卡住——不是不会写而是不知道每道题背后在考什么、参数边界怎么处理、提交后为什么总有几个测试点过不去。这篇笔记就按我实际刷完这 72 道题的路径把选题逻辑、环境搭建、典型题型的代码模板、以及最容易翻车的几个坑一次讲清楚。适合刚学完一门语言、想通过 PAT 风格题目把编码能力拉到能打比赛或过机试水平的同学。2. 刷题环境与提交前的自检清单2.1 本地编译环境怎么配才不折腾PAT 题目对 C/C 的容忍度最高Java 和 Python 也能用但部分题目的时间限制对脚本语言不太友好。我一般建议主力用 C17本地用 g 编译编辑器随意。下面是一个最小可用的编译命令模板保存为run.sh放在题目目录下每次改完代码直接跑#!/bin/bash # 编译当前目录下的 main.cpp开启常用警告输出到 main g -stdc17 -O2 -Wall -Wextra -o main main.cpp if [ $? -ne 0 ]; then echo 编译失败检查语法错误 exit 1 fi # 用题目给的样例输入跑一遍 ./main input.txt逻辑说明-stdc17保证能用结构化绑定和auto推导-O2在本地跑大数据量时更接近评测机速度-Wall -Wextra把警告当半个错误看很多“本地能过、提交 WA”的问题就是隐式类型转换或未初始化变量导致的。input.txt里放题目样例每次改完直接bash run.sh省去反复手敲输入的时间。参数调整如果题目明确说“时间限制 200ms”把-O2换成-O3并加-marchnative在本地测极限但提交时不要带-marchnative评测机 CPU 不一定支持。Java 用户把编译命令换成javac Main.java java Main input.txt注意类名必须是Main。2.2 提交前必须过的五项检查这五项是我血泪经验攒出来的每次提交前花两分钟过一遍能省下大量“为什么只有 12 分”的困惑第一看输入规模。题目里 n 最大到 10^5 还是 10^6直接决定你用 O(n log n) 还是 O(n) 的算法。第二看输出格式。PAT 对行末空格和换行极其敏感多一个空格就是 WA。第三看边界值。n0、n1、全相同元素、空字符串这些情况手动构造一组测一下。第四看数据类型。累加和会不会超 int用long long还是__int128心里要有数。第五看多组输入的终止条件。有些题是读到 EOF有些是读到 0 结束读错就是死循环或提前退出。提示PAT 风格题目里输出格式错误Presentation Error通常直接算 WA不会单独给分所以行末空格和多余空行一定要在本地用cat -A看一遍。3. 前 30 题输入输出与模拟题的固定套路3.1 1001 到 1010 的输入解析模板1001 到 1010 这十道题基本都在考“怎么把输入数据正确读进来并按要求格式化输出”。常见输入形态有三种一行多个整数、多行每行一个字符串、以及带结束标记的变长输入。下面这个模板覆盖了这三种情况#include bits/stdc.h using namespace std; int main() { // 情况一一行多个整数数量已知 int a, b, c; while (cin a b c) { // 处理逻辑 cout a b c endl; } // 情况二多行字符串每行一个 string line; while (getline(cin, line)) { if (line.empty()) continue; // 跳过空行 // 处理 line } // 情况三读到特定值结束 int x; while (cin x x ! 0) { // 处理 x } return 0; }逻辑说明while (cin a b c)利用cin的布尔转换读到 EOF 或格式错误时自动退出适合“多组测试数据直到文件结束”的题型。getline和cin 混用时要注意缓冲区里残留的换行符必要时用cin.ignore()清掉。情况三的x ! 0是常见终止条件但有些题是x ! -1一定要看题。参数说明endl会强制刷新缓冲区数据量大时换成\n能快不少。如果题目要求“每组输出后跟一个空行”用cout ans \n\n不要用两个endl。3.2 模拟题的状态机写法1011 到 1030 里有一批模拟题典型特征是“按规则一步步更新状态最后输出结果”。这类题最怕逻辑分支写漏。我一般先把状态转移写成表格再照着表格写switch或if-else。比如一道常见的“石头剪刀布计分”模拟题状态表如下当前状态输入下一状态动作等待有效手势计分比较胜负等待无效字符等待跳过计分任意等待输出本局写代码时把“等待”和“计分”做成两个函数主循环只负责读输入和调函数逻辑会清晰很多。模拟题另一个坑是“一轮结束后要不要重置计数器”这个看题目描述里有没有“每轮独立”字样没有的话通常要累加。3.3 字符串处理的三个必会函数1031 到 1040 集中考字符串。C 里必须熟练的是substr、find和stoi/stod。substr(pos, len)从 pos 开始取 len 个字符len 省略时取到末尾。find返回第一次出现的下标找不到返回string::npos。stoi把字符串转整数遇到非数字会抛异常稳妥写法是先用all_of判断是否全数字。string s 2024-01-15; // 提取年份 string year s.substr(0, 4); // 2024 // 找分隔符位置 size_t pos s.find(-); if (pos ! string::npos) { string month s.substr(pos 1, 2); // 01 } // 安全转整数 if (!s.empty() all_of(s.begin(), s.end(), ::isdigit)) { int val stoi(s); }逻辑说明substr的第二个参数是长度不是结束下标这是新手最容易搞混的地方。find返回size_t和int比较时会有符号问题统一用size_t或auto接。stoi前做全数字判断能避免程序崩溃PAT 里输入保证合法时也可以不判但养成习惯没坏处。4. 中间 30 题排序、查找与动态规划入门4.1 排序题的比较函数怎么写才不翻车1041 到 1055 里排序题扎堆。sort默认升序降序用greaterint()但结构体排序必须自定义比较函数。下面是一个典型的学生成绩排序要求总分降序、总分相同按学号升序struct Student { string id; int total; }; // 比较函数总分高的在前总分相同学号小的在前 bool cmp(const Student a, const Student b) { if (a.total ! b.total) return a.total b.total; return a.id b.id; } int main() { vectorStudent v {{S002, 90}, {S001, 90}, {S003, 85}}; sort(v.begin(), v.end(), cmp); for (auto s : v) cout s.id s.total \n; return 0; }逻辑说明比较函数必须满足严格弱序即cmp(a,a)必须返回 false。写成a.total b.total会导致未定义行为某些评测机上直接段错误。多关键字排序就按优先级依次写if最后一个条件用或返回。参数说明sort的时间复杂度是 O(n log n)n 到 10^5 完全没问题。如果题目要求稳定排序相同元素保持原顺序用stable_sort但会稍慢。结构体较大时比较函数参数用const避免拷贝。4.2 二分查找的边界控制1056 到 1065 会出现“在有序数组中找第一个大于等于 x 的位置”这类题。C 的lower_bound和upper_bound直接可用但手写二分能帮你理解边界。下面这个模板找第一个大于等于 target 的下标int lowerBound(vectorint nums, int target) { int left 0, right nums.size(); // 注意 right 取 size 不是 size-1 while (left right) { int mid left (right - left) / 2; // 防溢出 if (nums[mid] target) { left mid 1; } else { right mid; } } return left; // 可能等于 size表示所有元素都小于 target }逻辑说明right初始化为size而不是size-1这样区间是左闭右开[left, right)循环结束时left right就是答案。mid用left (right - left) / 2防止left right溢出。如果找最后一个小于等于 target 的位置把条件反过来返回left - 1。参数说明lower_bound返回迭代器减去begin()得到下标。题目要求“找不到输出 -1”时判断返回值是否等于size。4.3 动态规划入门从 1066 到 1072 的状态定义最后几道题开始涉及 DP典型的是“最大子段和”和“最长上升子序列”。DP 的核心是状态定义和转移方程写代码前先在纸上把这两样写清楚。以最大子段和为例// dp[i] 表示以 nums[i] 结尾的最大子段和 int maxSubArray(vectorint nums) { int n nums.size(); vectorint dp(n); dp[0] nums[0]; int ans dp[0]; for (int i 1; i n; i) { // 要么接在前一个后面要么自己重新开始 dp[i] max(nums[i], dp[i-1] nums[i]); ans max(ans, dp[i]); } return ans; }逻辑说明dp[i]必须“以 i 结尾”这样转移时才能保证子段连续。如果定义成“前 i 个元素里的最大子段和”转移方程会复杂很多。初始化dp[0] nums[0]然后从 1 开始遍历。答案在遍历过程中更新因为最大子段不一定以最后一个元素结尾。参数说明空间可以优化成 O(1)只保留prev和cur两个变量。如果题目要求输出子段起止下标额外记录start和end更新ans时同步更新。5. 避坑与排查这五类错误我几乎每道题都犯过5.1 输出格式错误行末空格和多余换行现象本地跑样例输出和题目一模一样提交后一半测试点 WA。原因PAT 评测机对行末空格零容忍cout a b 最后多一个空格就是错。解决用bool first标记控制分隔符或者把结果存进 vector 再统一输出。vectorint res {1, 2, 3}; for (size_t i 0; i res.size(); i) { if (i 0) cout ; cout res[i]; } cout \n;5.2 数组越界n0 和 n1 没单独处理现象提交后报“运行时错误”或“段错误”。原因代码里写了nums[0]但没判断数组是否为空或者循环从 1 开始但 n1 时直接跳过。解决所有访问nums[0]的地方前面加if (nums.empty()) return 0;循环边界用i n而不是i n。5.3 整数溢出累加和用了 int现象大数据量测试点结果变成负数。原因n 个 10^9 相加超过 int 上限约 2.1×10^9。解决累加变量声明为long long输出用%lld或cout。如果题目数据范围到 10^18考虑__int128或 Python。5.4 多组输入没清空全局变量现象第一组数据正确第二组开始结果错乱。原因全局数组或vector没在每组开始前清空。解决把变量定义在循环内部或者每组开头手动fill/clear。用memset时注意只能清零或置 -1置其他值会出错。5.5 浮点数比较用了 现象几何题或概率题结果差 0.000001 被判错。原因浮点数运算有精度误差a b几乎永远不成立。解决用fabs(a - b) 1e-8判断相等输出时按题目要求保留小数位printf(%.2f)会自动四舍五入。6. 把 72 题刷出三倍效果我的复盘与重刷策略刷完 1001 到 1072 只是第一步真正拉开差距的是刷完之后怎么复盘。我自己的习惯是每道题提交通过后不急着下一题先做三件事第一把代码里所有“侥幸通过”的地方标出来比如没处理 n0 但测试数据恰好没有 n0这种地方下次一定翻车第二去网上搜一下这道题有没有更优解法PAT 题目通常有 O(n) 和 O(n log n) 两种做法都写一遍第三把题目按考点分类归档比如“字符串模拟”“排序结构体”“DP滚动数组”每类攒够五道后回头横向对比。重刷的时候不要按题号顺序按考点刷。比如今天专门刷“二分查找”类把 1056 到 1065 里所有二分题连做一遍你会发现边界条件的写法高度相似形成肌肉记忆后比赛时手写二分基本不会错。另一个技巧是限时训练第一遍刷不限时重刷时给自己定 25 分钟一道模拟机试节奏。超时的题目标记出来分析是思路卡住还是编码太慢。最后说一个我踩过的坑不要盲目追求刷题数量。我曾经一天刷 15 道简单题感觉进度飞快但遇到中等题还是不会。后来改成一天精刷 3 道每道都写题解、分析复杂度、构造边界数据反而提升更快。这套 1001 到 1072 的题单如果你能按上面的方法精刷两遍配合每类考点的专项突破应付大多数机试和竞赛初赛是够用的。希望帮到你。本文还有配套的精品资源点击获取