尧图网页设计 
简介这份资源是《信息学奥赛一本通C》算法与数据结构部分的配套题目与测试数据合集面向青少年编程学习者、信息学奥赛参赛者及辅导教师用于系统刷题、验证程序正确性与赛前集训。压缩包共约2000个文件整体68.52MB其中1561个.in输入文件与1489个.out输出文件构成完整测试用例182个cpp与175个pas源码提供C和Pascal参考实现另有74个ans答案、44个bat批处理脚本及少量pdf、txt、doc说明文档便于批量评测与对照学习。内容覆盖排序、查找、图论、动态规划、回溯与贪心等算法以及数组、链表、栈、队列、树、哈希表、堆、图等数据结构题目类型丰富、数据齐全。目前已有3172人学习下载适合按知识点逐题练习、比对输出结果并排查错误是备赛与日常训练中可直接使用的题库资源。1. 信息学奥赛一本通C算法与数据结构题目和测试数据怎么用信息学奥赛一本通C的算法和数据结构部分是很多竞赛教练和自学选手绕不开的一本“题库型教材”。它不像严蔚敏数据结构C语言版pdf那样偏理论推导也不像数据结构与算法知识点归纳那样只给结论而是把每个算法点拆成若干道可提交的题目再配一套测试数据让你在反复WA和AC之间把算法真正吃透。问题在于很多人拿到这本书或它的题目列表后卡在“知道要刷题但不知道怎么组织训练”这一步题目顺序怎么排、测试数据怎么造、本地怎么对拍、哪些题值得反复写。这篇内容面向正在用这本书带课或自学的C学习者把算法和数据结构部分的题目与测试数据从选题、环境、造数据到对拍验证走一遍能复现的路径。2. 把一本通题目拆成可执行的训练单元2.1 先分清“算法题”和“数据结构题”的边界一本通C的算法和数据结构部分题目大致可以分成两类。一类是纯算法题比如贪心算法、暴力枚举算法、剪枝算法、归并排序算法、KMP算法、A*算法这些题的核心是“想清楚步骤”数据结构只是辅助。另一类是数据结构题比如前缀和、双端队列、并查集、线段树、树状数组这些题的核心是“选对结构”算法反而是模板化的。我一般会按“先算法后结构”的顺序带人。原因是算法题对C语法要求低容易建立正反馈数据结构题一旦结构选错调试成本会翻倍。具体到一本通的章节可以这样映射训练阶段一本通常见章节核心考点建议题量入门顺序结构、选择结构输入输出、边界判断1520算法基础循环、数组、函数暴力枚举、模拟2030算法进阶递推、递归、贪心状态转移、局部最优1520数据结构栈、队列、链表线性结构操作1520数据结构进阶树、图、并查集遍历、连通性2025算法综合排序、查找、动态规划归并排序、二分、DP2530这个表不是让你从头刷到尾而是让你先定位自己卡在哪一层。如果你连暴力枚举算法都写不利索直接上A*算法原理图那种内容基本是浪费时间。2.2 用VSCode配置C/C环境跑通第一道题热词里“vscode配置c/c环境”和“vscode c”出现频率很高说明很多人卡在环境上。一本通的题目大多是单文件、标准输入输出不需要复杂工程。用VSCode配MinGW-w64就够了不需要上Visual Studio。先确认编译器可用g --version如果输出类似g (MinGW-W64 x86_64-ucrt-posix-seh) 13.2.0说明编译器就绪。然后建一个工作目录写第一道题// 一本通入门题输入两个整数输出它们的和 #include iostream using namespace std; int main() { int a, b; cin a b; // 标准输入读取两个整数 cout a b endl; // 输出和并换行 return 0; }编译运行g -stdc17 -O2 -Wall -o sum sum.cpp ./sum参数说明-stdc17指定标准一本通大部分题用C11以上都能过-O2开优化模拟赛和正式比赛都建议加-Wall打开警告能提前发现未初始化变量、类型转换问题。输入3 5输出8环境就算通了。注意Windows下如果g不是内部命令检查MinGW的bin目录是否加进PATH。不要用visual c redistributable那套运行库思路去解决编译问题那是运行已编译程序用的不是编译环境。2.3 测试数据从哪来三种可靠来源一本通配套的测试数据通常以.in和.out成对出现命名如1.in、1.out。如果你手头没有完整数据包可以按下面三种方式补第一种直接用书后附的样例。优点是权威缺点是数据量小覆盖不到边界。第二种自己写生成器造数据。第三种用对拍程序验证自己的输出。我一般会先跑样例再补边界。比如一道“求区间和”的题样例只给了n5我会补n1、n100000、所有数为负数、区间跨越整个数组这几种情况。这些数据不需要多但能暴露前缀和数组越界、int溢出、long long没开这些问题。3. 用生成器和对拍把测试数据跑成闭环3.1 写一个可复用的随机数据生成器C随机数是一本通里容易被忽略的点。很多人生成器直接用rand()结果在Windows上最大只有32767造不出大数据。正确做法是用mt19937加uniform_int_distribution。// gen.cpp生成n个整数的测试数据 #include bits/stdc.h using namespace std; int main(int argc, char* argv[]) { int seed argc 1 ? atoi(argv[1]) : 1; mt19937 rng(seed); // 用种子初始化梅森旋转引擎 uniform_int_distributionint nDist(1, 100000); uniform_int_distributionint vDist(-10000, 10000); int n nDist(rng); cout n endl; for (int i 0; i n; i) { cout vDist(rng) \n[i n - 1]; } return 0; }逻辑说明seed从命令行传入保证每次生成可复现nDist控制数据规模vDist控制数值范围。编译后这样用g -stdc17 -O2 -o gen gen.cpp ./gen 1 1.in ./gen 2 2.in参数怎么改如果题目要求n不超过1000就把nDist改成uniform_int_distributionint nDist(1, 1000)如果要求输出严格递增就在生成后加sort。不要用rand()%100000那个分布不均匀容易造出重复数据。3.2 对拍脚本用暴力程序验证优化程序对拍是算法竞赛里最实用的后悔药。思路是写一个暴力枚举算法程序brute.cpp再写你的优化程序fast.cpp用同一组输入跑比较输出。#!/bin/bash # 对拍脚本brute和fast对拍1000轮 g -stdc17 -O2 -o brute brute.cpp g -stdc17 -O2 -o fast fast.cpp g -stdc17 -O2 -o gen gen.cpp for i in $(seq 1 1000); do ./gen $i test.in ./brute test.in brute.out ./fast test.in fast.out if ! diff -q brute.out fast.out /dev/null; then echo WA on test $i cat test.in break fi done echo done逻辑说明seq 1 1000控制对拍轮数diff -q只判断是否相同不输出差异内容发现不同就打印输入并退出。参数调整如果暴力程序跑得慢把轮数降到100如果数据规模大把gen里的范围调小先保证逻辑正确再放大。注意对拍只能验证你想到的边界不能证明程序绝对正确。正式比赛前还是要手造几组极端数据比如全相同、全逆序、最大规模。3.3 归并排序和KMP的测试数据怎么设计归并排序算法和KMP算法是一本通里两个典型考点。归并排序的测试数据要覆盖已有序、完全逆序、大量重复元素、n1、n2。KMP的测试数据要覆盖模式串在文本串开头、结尾、不存在、完全匹配、模式串比文本串长。我一般会为这两类题单独写生成器。归并排序生成器重点控制“重复率”KMP生成器重点控制“字符集大小”。字符集越小失配越频繁越能暴露next数组的边界问题。// kmp_gen.cpp生成小字符集的KMP测试数据 #include bits/stdc.h using namespace std; int main(int argc, char* argv[]) { int seed argc 1 ? atoi(argv[1]) : 1; mt19937 rng(seed); uniform_int_distributionint lenDist(1, 1000); string chars ab; // 小字符集增加失配概率 uniform_int_distributionint chDist(0, chars.size() - 1); int n lenDist(rng), m lenDist(rng); string s, t; for (int i 0; i n; i) s chars[chDist(rng)]; for (int i 0; i m; i) t chars[chDist(rng)]; cout s endl t endl; return 0; }这个生成器把字符集限制在a和bKMP在这种数据上最容易出现next数组回退错误。跑对拍时暴力程序用find或双层循环优化程序用KMP很快就能发现问题。4. 避坑一本通刷题和造数据时最容易翻车的五件事4.1 现象本地样例过提交全WA原因一本通的测试数据往往包含多组输入而题目描述里没写“多组数据”。很多人只读一组就输出导致后面全错。解决看题目是否有“输入包含多组数据”或“读到文件末尾”的提示。如果有用while (cin n)循环处理。4.2 现象数组开得和题目范围一样大结果RE原因一本通很多题目的实际数据比题面标注的大或者有隐藏的n1访问。解决数组至少开题目范围的1.5倍全局数组更稳。比如题目说n100000就开int a[150005]。4.3 现象归并排序结果正确但超时原因用了vector的insert或erase或者每次合并都新建数组。解决归并排序必须用临时数组一次性合并不要用动态容器频繁扩容。临时数组也开全局避免栈溢出。4.4 现象KMP的next数组在模式串长度为1时崩溃原因next[0]初始化后循环从i1开始但长度为1时循环不执行后续匹配逻辑却访问了next[1]。解决把next数组开成m1并确保next[0]-1或next[0]0的约定在整个程序里一致。4.5 现象对拍脚本在Windows下跑不了原因seq、diff、./这些是Linux/macOS写法。解决用Git Bash或WSL跑对拍脚本或者在Windows下改用.bat脚本用fc代替diff。不要用c#调用c出现access violation c0000005那种跨语言调试思路来解决对拍问题那是另一个场景。5. 用前缀和与双端队列把数据结构题跑出“手感”5.1 前缀和从暴力到O(1)查询的验证方法前缀和是一本通里最容易被低估的数据结构。很多人觉得“不就是开个数组累加吗”但真正写的时候边界处理经常翻车。我一般会要求先写暴力再写前缀和然后对拍。// 前缀和多次查询区间和 #include bits/stdc.h using namespace std; const int MAXN 100005; long long a[MAXN], pre[MAXN]; // pre[i] a[1] ... a[i] int main() { int n, q; cin n q; for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; // 递推构造前缀和 } while (q--) { int l, r; cin l r; cout pre[r] - pre[l - 1] endl; // O(1)查询 } return 0; }参数说明pre数组必须用long long因为n个int相加可能溢出下标从1开始pre[0]0这样l1时pre[l-1]不会越界。验证方法写一个暴力程序每次查询循环累加对拍1000轮。如果前缀和写错通常错在pre[l-1]写成pre[l]或者数组没开够。5.2 双端队列滑动窗口最大值的测试数据设计双端队列在一本通里通常出现在“滑动窗口”类题目。这类题的测试数据要覆盖窗口大小为1、窗口大小等于数组长度、所有元素相同、严格递增、严格递减。// 滑动窗口最大值双端队列实现 #include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; dequeint dq; // 存下标对应值单调递减 for (int i 0; i n; i) { while (!dq.empty() dq.front() i - k) dq.pop_front(); // 移除过期 while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); // 维护单调 dq.push_back(i); if (i k - 1) cout a[dq.front()] ; } cout endl; return 0; }逻辑说明dq存的是下标a[dq.front()]是当前窗口最大值第一个while保证窗口左边界不超过i-k1第二个while保证队列单调递减。测试数据设计用生成器造n100000、k1和kn两组再造一组所有元素相同的检查输出是否稳定。如果输出个数不对通常是i k - 1这个条件写错。5.3 把“刷题量”变成“可验证的通过率”很多人刷一本通只数做了多少题不统计通过率。我一般会建一个简单表格记录每道题的提交次数、错误类型、是否对拍通过。错误类型分WA逻辑错、TLE复杂度错、RE数组/指针错、CE语法错。一周后看哪类错误最多针对性补。题目考点提交次数错误类型对拍轮数状态区间和前缀和3WA1000通过滑动窗口双端队列5TLE500通过字符串匹配KMP4RE1000通过逆序对归并排序2WA1000通过这张表比“今天刷了10道题”有用得多。它告诉你你的时间到底花在哪个坑里。6. 用A*和剪枝算法做一次综合验证A算法和剪枝算法在一本通里属于进阶内容适合用来检验前面所有基础是否扎实。A的核心是估价函数剪枝的核心是搜索顺序。这两个算法如果写错通常不是语法问题而是对问题建模的理解偏差。我一般会拿一道“八数码”或“迷宫最短路”来收尾。先写暴力BFS再写A*用同一组测试数据比较步数和时间。如果A*比BFS还慢说明估价函数设计有问题或者优先队列的比较逻辑写反了。// A*八数码估价函数用曼哈顿距离 #include bits/stdc.h using namespace std; struct State { string board; int g, h; bool operator(const State o) const { return g h o.g o.h; // 小根堆 } }; int manhattan(const string s) { int sum 0; for (int i 0; i 9; i) { if (s[i] 0) continue; int num s[i] - 1; sum abs(i / 3 - num / 3) abs(i % 3 - num % 3); } return sum; } int main() { string start 123456780; // 目标状态 string goal 123456780; // 实际使用时从输入读取start priority_queueState pq; unordered_mapstring, int dist; pq.push({start, 0, manhattan(start)}); dist[start] 0; while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.board goal) { cout cur.g endl; break; } if (cur.g dist[cur.board]) continue; // 剪枝旧状态 int pos cur.board.find(0); int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nx pos / 3 dx[d]; int ny pos % 3 dy[d]; if (nx 0 || nx 3 || ny 0 || ny 3) continue; string nxt cur.board; swap(nxt[pos], nxt[nx * 3 ny]); if (!dist.count(nxt) || cur.g 1 dist[nxt]) { dist[nxt] cur.g 1; pq.push({nxt, cur.g 1, manhattan(nxt)}); } } } return 0; }这段代码里manhattan是估价函数g是实际步数h是曼哈顿距离。operator里用gh o.go.h是为了让优先队列变成小根堆。剪枝体现在if (cur.g dist[cur.board]) continue;跳过已经找到更短路径的旧状态。验证方法先用BFS跑一遍记录最短步数再用A跑比较结果是否一致。如果A结果更短说明BFS写错了如果A结果更长说明估价函数不满足可采纳性。测试数据用随机打乱的八数码跑100组统计平均扩展节点数。A的扩展节点数应该明显少于BFS否则估价函数需要调整。我自己的习惯是每学完一个算法必须用对拍验证一次再用A*或剪枝做一次综合。一本通C的算法和数据结构部分题目和测试数据只是素材真正让你进步的是“写—错—对拍—改—再验证”这个闭环。希望帮到你。本文还有配套的精品资源点击获取 信息学奥赛一本通C++算法与数据结构题目和测试数据使用指南
简介这份资源是《信息学奥赛一本通C》算法与数据结构部分的配套题目与测试数据合集面向青少年编程学习者、信息学奥赛参赛者及辅导教师用于系统刷题、验证程序正确性与赛前集训。压缩包共约2000个文件整体68.52MB其中1561个.in输入文件与1489个.out输出文件构成完整测试用例182个cpp与175个pas源码提供C和Pascal参考实现另有74个ans答案、44个bat批处理脚本及少量pdf、txt、doc说明文档便于批量评测与对照学习。内容覆盖排序、查找、图论、动态规划、回溯与贪心等算法以及数组、链表、栈、队列、树、哈希表、堆、图等数据结构题目类型丰富、数据齐全。目前已有3172人学习下载适合按知识点逐题练习、比对输出结果并排查错误是备赛与日常训练中可直接使用的题库资源。1. 信息学奥赛一本通C算法与数据结构题目和测试数据怎么用信息学奥赛一本通C的算法和数据结构部分是很多竞赛教练和自学选手绕不开的一本“题库型教材”。它不像严蔚敏数据结构C语言版pdf那样偏理论推导也不像数据结构与算法知识点归纳那样只给结论而是把每个算法点拆成若干道可提交的题目再配一套测试数据让你在反复WA和AC之间把算法真正吃透。问题在于很多人拿到这本书或它的题目列表后卡在“知道要刷题但不知道怎么组织训练”这一步题目顺序怎么排、测试数据怎么造、本地怎么对拍、哪些题值得反复写。这篇内容面向正在用这本书带课或自学的C学习者把算法和数据结构部分的题目与测试数据从选题、环境、造数据到对拍验证走一遍能复现的路径。2. 把一本通题目拆成可执行的训练单元2.1 先分清“算法题”和“数据结构题”的边界一本通C的算法和数据结构部分题目大致可以分成两类。一类是纯算法题比如贪心算法、暴力枚举算法、剪枝算法、归并排序算法、KMP算法、A*算法这些题的核心是“想清楚步骤”数据结构只是辅助。另一类是数据结构题比如前缀和、双端队列、并查集、线段树、树状数组这些题的核心是“选对结构”算法反而是模板化的。我一般会按“先算法后结构”的顺序带人。原因是算法题对C语法要求低容易建立正反馈数据结构题一旦结构选错调试成本会翻倍。具体到一本通的章节可以这样映射训练阶段一本通常见章节核心考点建议题量入门顺序结构、选择结构输入输出、边界判断1520算法基础循环、数组、函数暴力枚举、模拟2030算法进阶递推、递归、贪心状态转移、局部最优1520数据结构栈、队列、链表线性结构操作1520数据结构进阶树、图、并查集遍历、连通性2025算法综合排序、查找、动态规划归并排序、二分、DP2530这个表不是让你从头刷到尾而是让你先定位自己卡在哪一层。如果你连暴力枚举算法都写不利索直接上A*算法原理图那种内容基本是浪费时间。2.2 用VSCode配置C/C环境跑通第一道题热词里“vscode配置c/c环境”和“vscode c”出现频率很高说明很多人卡在环境上。一本通的题目大多是单文件、标准输入输出不需要复杂工程。用VSCode配MinGW-w64就够了不需要上Visual Studio。先确认编译器可用g --version如果输出类似g (MinGW-W64 x86_64-ucrt-posix-seh) 13.2.0说明编译器就绪。然后建一个工作目录写第一道题// 一本通入门题输入两个整数输出它们的和 #include iostream using namespace std; int main() { int a, b; cin a b; // 标准输入读取两个整数 cout a b endl; // 输出和并换行 return 0; }编译运行g -stdc17 -O2 -Wall -o sum sum.cpp ./sum参数说明-stdc17指定标准一本通大部分题用C11以上都能过-O2开优化模拟赛和正式比赛都建议加-Wall打开警告能提前发现未初始化变量、类型转换问题。输入3 5输出8环境就算通了。注意Windows下如果g不是内部命令检查MinGW的bin目录是否加进PATH。不要用visual c redistributable那套运行库思路去解决编译问题那是运行已编译程序用的不是编译环境。2.3 测试数据从哪来三种可靠来源一本通配套的测试数据通常以.in和.out成对出现命名如1.in、1.out。如果你手头没有完整数据包可以按下面三种方式补第一种直接用书后附的样例。优点是权威缺点是数据量小覆盖不到边界。第二种自己写生成器造数据。第三种用对拍程序验证自己的输出。我一般会先跑样例再补边界。比如一道“求区间和”的题样例只给了n5我会补n1、n100000、所有数为负数、区间跨越整个数组这几种情况。这些数据不需要多但能暴露前缀和数组越界、int溢出、long long没开这些问题。3. 用生成器和对拍把测试数据跑成闭环3.1 写一个可复用的随机数据生成器C随机数是一本通里容易被忽略的点。很多人生成器直接用rand()结果在Windows上最大只有32767造不出大数据。正确做法是用mt19937加uniform_int_distribution。// gen.cpp生成n个整数的测试数据 #include bits/stdc.h using namespace std; int main(int argc, char* argv[]) { int seed argc 1 ? atoi(argv[1]) : 1; mt19937 rng(seed); // 用种子初始化梅森旋转引擎 uniform_int_distributionint nDist(1, 100000); uniform_int_distributionint vDist(-10000, 10000); int n nDist(rng); cout n endl; for (int i 0; i n; i) { cout vDist(rng) \n[i n - 1]; } return 0; }逻辑说明seed从命令行传入保证每次生成可复现nDist控制数据规模vDist控制数值范围。编译后这样用g -stdc17 -O2 -o gen gen.cpp ./gen 1 1.in ./gen 2 2.in参数怎么改如果题目要求n不超过1000就把nDist改成uniform_int_distributionint nDist(1, 1000)如果要求输出严格递增就在生成后加sort。不要用rand()%100000那个分布不均匀容易造出重复数据。3.2 对拍脚本用暴力程序验证优化程序对拍是算法竞赛里最实用的后悔药。思路是写一个暴力枚举算法程序brute.cpp再写你的优化程序fast.cpp用同一组输入跑比较输出。#!/bin/bash # 对拍脚本brute和fast对拍1000轮 g -stdc17 -O2 -o brute brute.cpp g -stdc17 -O2 -o fast fast.cpp g -stdc17 -O2 -o gen gen.cpp for i in $(seq 1 1000); do ./gen $i test.in ./brute test.in brute.out ./fast test.in fast.out if ! diff -q brute.out fast.out /dev/null; then echo WA on test $i cat test.in break fi done echo done逻辑说明seq 1 1000控制对拍轮数diff -q只判断是否相同不输出差异内容发现不同就打印输入并退出。参数调整如果暴力程序跑得慢把轮数降到100如果数据规模大把gen里的范围调小先保证逻辑正确再放大。注意对拍只能验证你想到的边界不能证明程序绝对正确。正式比赛前还是要手造几组极端数据比如全相同、全逆序、最大规模。3.3 归并排序和KMP的测试数据怎么设计归并排序算法和KMP算法是一本通里两个典型考点。归并排序的测试数据要覆盖已有序、完全逆序、大量重复元素、n1、n2。KMP的测试数据要覆盖模式串在文本串开头、结尾、不存在、完全匹配、模式串比文本串长。我一般会为这两类题单独写生成器。归并排序生成器重点控制“重复率”KMP生成器重点控制“字符集大小”。字符集越小失配越频繁越能暴露next数组的边界问题。// kmp_gen.cpp生成小字符集的KMP测试数据 #include bits/stdc.h using namespace std; int main(int argc, char* argv[]) { int seed argc 1 ? atoi(argv[1]) : 1; mt19937 rng(seed); uniform_int_distributionint lenDist(1, 1000); string chars ab; // 小字符集增加失配概率 uniform_int_distributionint chDist(0, chars.size() - 1); int n lenDist(rng), m lenDist(rng); string s, t; for (int i 0; i n; i) s chars[chDist(rng)]; for (int i 0; i m; i) t chars[chDist(rng)]; cout s endl t endl; return 0; }这个生成器把字符集限制在a和bKMP在这种数据上最容易出现next数组回退错误。跑对拍时暴力程序用find或双层循环优化程序用KMP很快就能发现问题。4. 避坑一本通刷题和造数据时最容易翻车的五件事4.1 现象本地样例过提交全WA原因一本通的测试数据往往包含多组输入而题目描述里没写“多组数据”。很多人只读一组就输出导致后面全错。解决看题目是否有“输入包含多组数据”或“读到文件末尾”的提示。如果有用while (cin n)循环处理。4.2 现象数组开得和题目范围一样大结果RE原因一本通很多题目的实际数据比题面标注的大或者有隐藏的n1访问。解决数组至少开题目范围的1.5倍全局数组更稳。比如题目说n100000就开int a[150005]。4.3 现象归并排序结果正确但超时原因用了vector的insert或erase或者每次合并都新建数组。解决归并排序必须用临时数组一次性合并不要用动态容器频繁扩容。临时数组也开全局避免栈溢出。4.4 现象KMP的next数组在模式串长度为1时崩溃原因next[0]初始化后循环从i1开始但长度为1时循环不执行后续匹配逻辑却访问了next[1]。解决把next数组开成m1并确保next[0]-1或next[0]0的约定在整个程序里一致。4.5 现象对拍脚本在Windows下跑不了原因seq、diff、./这些是Linux/macOS写法。解决用Git Bash或WSL跑对拍脚本或者在Windows下改用.bat脚本用fc代替diff。不要用c#调用c出现access violation c0000005那种跨语言调试思路来解决对拍问题那是另一个场景。5. 用前缀和与双端队列把数据结构题跑出“手感”5.1 前缀和从暴力到O(1)查询的验证方法前缀和是一本通里最容易被低估的数据结构。很多人觉得“不就是开个数组累加吗”但真正写的时候边界处理经常翻车。我一般会要求先写暴力再写前缀和然后对拍。// 前缀和多次查询区间和 #include bits/stdc.h using namespace std; const int MAXN 100005; long long a[MAXN], pre[MAXN]; // pre[i] a[1] ... a[i] int main() { int n, q; cin n q; for (int i 1; i n; i) { cin a[i]; pre[i] pre[i - 1] a[i]; // 递推构造前缀和 } while (q--) { int l, r; cin l r; cout pre[r] - pre[l - 1] endl; // O(1)查询 } return 0; }参数说明pre数组必须用long long因为n个int相加可能溢出下标从1开始pre[0]0这样l1时pre[l-1]不会越界。验证方法写一个暴力程序每次查询循环累加对拍1000轮。如果前缀和写错通常错在pre[l-1]写成pre[l]或者数组没开够。5.2 双端队列滑动窗口最大值的测试数据设计双端队列在一本通里通常出现在“滑动窗口”类题目。这类题的测试数据要覆盖窗口大小为1、窗口大小等于数组长度、所有元素相同、严格递增、严格递减。// 滑动窗口最大值双端队列实现 #include bits/stdc.h using namespace std; int main() { int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; dequeint dq; // 存下标对应值单调递减 for (int i 0; i n; i) { while (!dq.empty() dq.front() i - k) dq.pop_front(); // 移除过期 while (!dq.empty() a[dq.back()] a[i]) dq.pop_back(); // 维护单调 dq.push_back(i); if (i k - 1) cout a[dq.front()] ; } cout endl; return 0; }逻辑说明dq存的是下标a[dq.front()]是当前窗口最大值第一个while保证窗口左边界不超过i-k1第二个while保证队列单调递减。测试数据设计用生成器造n100000、k1和kn两组再造一组所有元素相同的检查输出是否稳定。如果输出个数不对通常是i k - 1这个条件写错。5.3 把“刷题量”变成“可验证的通过率”很多人刷一本通只数做了多少题不统计通过率。我一般会建一个简单表格记录每道题的提交次数、错误类型、是否对拍通过。错误类型分WA逻辑错、TLE复杂度错、RE数组/指针错、CE语法错。一周后看哪类错误最多针对性补。题目考点提交次数错误类型对拍轮数状态区间和前缀和3WA1000通过滑动窗口双端队列5TLE500通过字符串匹配KMP4RE1000通过逆序对归并排序2WA1000通过这张表比“今天刷了10道题”有用得多。它告诉你你的时间到底花在哪个坑里。6. 用A*和剪枝算法做一次综合验证A算法和剪枝算法在一本通里属于进阶内容适合用来检验前面所有基础是否扎实。A的核心是估价函数剪枝的核心是搜索顺序。这两个算法如果写错通常不是语法问题而是对问题建模的理解偏差。我一般会拿一道“八数码”或“迷宫最短路”来收尾。先写暴力BFS再写A*用同一组测试数据比较步数和时间。如果A*比BFS还慢说明估价函数设计有问题或者优先队列的比较逻辑写反了。// A*八数码估价函数用曼哈顿距离 #include bits/stdc.h using namespace std; struct State { string board; int g, h; bool operator(const State o) const { return g h o.g o.h; // 小根堆 } }; int manhattan(const string s) { int sum 0; for (int i 0; i 9; i) { if (s[i] 0) continue; int num s[i] - 1; sum abs(i / 3 - num / 3) abs(i % 3 - num % 3); } return sum; } int main() { string start 123456780; // 目标状态 string goal 123456780; // 实际使用时从输入读取start priority_queueState pq; unordered_mapstring, int dist; pq.push({start, 0, manhattan(start)}); dist[start] 0; while (!pq.empty()) { State cur pq.top(); pq.pop(); if (cur.board goal) { cout cur.g endl; break; } if (cur.g dist[cur.board]) continue; // 剪枝旧状态 int pos cur.board.find(0); int dx[] {-1, 1, 0, 0}; int dy[] {0, 0, -1, 1}; for (int d 0; d 4; d) { int nx pos / 3 dx[d]; int ny pos % 3 dy[d]; if (nx 0 || nx 3 || ny 0 || ny 3) continue; string nxt cur.board; swap(nxt[pos], nxt[nx * 3 ny]); if (!dist.count(nxt) || cur.g 1 dist[nxt]) { dist[nxt] cur.g 1; pq.push({nxt, cur.g 1, manhattan(nxt)}); } } } return 0; }这段代码里manhattan是估价函数g是实际步数h是曼哈顿距离。operator里用gh o.go.h是为了让优先队列变成小根堆。剪枝体现在if (cur.g dist[cur.board]) continue;跳过已经找到更短路径的旧状态。验证方法先用BFS跑一遍记录最短步数再用A跑比较结果是否一致。如果A结果更短说明BFS写错了如果A结果更长说明估价函数不满足可采纳性。测试数据用随机打乱的八数码跑100组统计平均扩展节点数。A的扩展节点数应该明显少于BFS否则估价函数需要调整。我自己的习惯是每学完一个算法必须用对拍验证一次再用A*或剪枝做一次综合。一本通C的算法和数据结构部分题目和测试数据只是素材真正让你进步的是“写—错—对拍—改—再验证”这个闭环。希望帮到你。本文还有配套的精品资源点击获取