看到“P3156 【深基15.例1】询问学号”这个标题做过洛谷“深基”系列的朋友应该都不陌生。这题在题库里标注为入门难度但它的地位很特殊——《深入浅出基础篇》第15章的例题正好卡在“数组”和“数据结构启蒙”的交接点上。很多新手在这道题上第一次接触“预处理查询”的思维模式也是第一次被卡在奇怪的输入输出细节上。这篇我结合自己刷题和带新人的经验把这道题的完整脉络重新捋一遍包括题目在问什么、为什么这么写、测试里容易踩哪些坑以及从这道题能顺带学到的几个通用技巧。1. 这题到底在考什么一次读懂“询问学号”的题意先说题目本身看透了之后你会发现它真的只是拿数组练手。1.1 题目逻辑拆解从“一行学号”到“一堆询问”题目有n个学生每个学生对应一个学号。输入先给一个整数n紧接着一行给出n个学号表示这n个学生的学号排列顺序。然后再给一个整数m意思是接下来有m次询问每次询问一个整数q要求输出第q个学生的学号。这里要注意题目表述里的一个关键区分它问的是“第q个学生”而不是“学号为q的学生”。一字之差做法就完全不同。如果是“学号为q”你必须遍历一遍看看谁是这个学号但“第q个学生”其实是在问下标也就是数组里第q个位置存的是什么。搞清楚这个题目的意图就非常清晰了——它是在考数组的下标对应关系。1.2 数据范围与时间压力评估“深基”系列的题目特点就是数据范围卡得恰到好处。这道题n和m的范围都在百万级别以内具体的范围不复杂你只需要知道它不允许你用过于笨拙的做法这意味着两层循环的O(n*m)复杂度会直接超时。所以题目本质上在引导你先把n个学号存下来形成一张“编号 - 学号”的对照表然后每次询问直接按下标取做到O(1)查询。1.3 为什么每个学号要用数组存而不是变量有新手会问能不能用n个变量a1、a2、a3分别存可以但前提是你提前知道n是多少而且n很小。一旦n变成一个变量你就没法在代码里写100万个变量名。数组的意义就在这里用同一个名字配合下标就能管理大量同类型数据。这道题就是让你亲手体验到这一点——哪怕是这么简单的题如果没有数组后续的m次询问根本没法高效完成。2. 从零到AC搭建数组存储与查询的完整流程这段我直接给你一套可复现的思路和代码不绕弯子。2.1 存储结构选型一维数组的天然匹配这题最朴素也最合适的结构就是C的一维数组。因为它就是一组学号的线性排列下标天然对应“第几个学生”。定义一个足够大的数组比如a[1000005]然后用循环读入n个学号存进去。这里有个很多新手会纠结的点学号会不会很大会不会超过int的范围题目里给的学号一般都在int范围内用int就好不需要long long。但数组长度一定要开够我习惯多用5个裕量防止手滑越界。这也是一个实务经验竞赛数组开大一点不扣分但开小了可能直接RE运行时错误。2.2 核心代码实现读入、存储、查询三步走下面这段代码是这道题最典型的解法我加了注释方便你对照#include bits/stdc.h using namespace std; const int MAXN 1000005; int a[MAXN]; int main() { int n, m, q; // 读入学生数量 cin n; // 读入n个学号存到数组a[1]到a[n] for (int i 1; i n; i) { cin a[i]; } // 读入询问次数 cin m; // 依次处理每次询问 for (int i 1; i m; i) { cin q; cout a[q] \n; } return 0; }这段代码里有两个细节值得单独说。第一个是数组下标从1开始。因为题目的“第q个学生”天然是从1计数的如果下标从0开始每次输出就要写成a[q-1]。两种写法都能过但从1开始更贴合题意也省得你每次询问都要做一次减法。不过你要清楚数组在内存里依然是从下标0开始分配的我们只是空出了a[0]不用而已。这在数据规模小的时候无所谓但养成“下标对应语义”的习惯后期做前缀和、差分这类题目时会省掉不少麻烦。第二个是输出用了\n而不是endl。在循环输出较多数据时endl除了换行还会强制刷新缓冲区速度慢很多。这道题m可能比较大用endl在极个别情况下会有超时风险\n是更稳的选择。这个技巧看起来小但实际影响刷题体验后面我细说。2.3 如果非要换个思路从“下标0”到“下标1”的转换也有不少人习惯用vector动态数组代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m, q; cin n; vectorint a(n 1); for (int i 1; i n; i) { cin a[i]; } cin m; while (m--) { cin q; cout a[q] \n; } return 0; }vector的写法多了一个好处不用自己维护数组大小动态扩容避免开小了越界。代价是相比静态数组多一点点性能和内存开销但这题完全无所谓。两种写法选一个自己顺手的即可不需要纠结。3. 让快读与缓冲机制成为你的默认选项这道题虽然用cin也能过但我见过不少人在类似题目上被卡在输入输出上。既然碰上了就把这层窗户纸捅破。3.1 cin为什么有时会“慢半拍”缓冲区同步的真相cin本身并不慢慢的是它默认与C标准IO同步。这个同步是为了让cin和scanf混用时不乱序但代价是每次输入都要做额外的同步检查。当输入量达到几十万甚至上百万时这个开销就非常明显了。想要关掉同步使用一条语句即可ios::sync_with_stdio(false);这条语句加了之后cin和scanf就不能混用了所以你的代码里要么全用cin要么全用scanf。另外还有一个细节cin默认是跟cout绑定的每次输入前会确保输出缓冲区被刷新。如果要处理大量数据可以再顺手解除绑定cin.tie(nullptr);这两句在竞赛代码里几乎是标配很多选手写代码第一行就加上成了肌肉记忆。我自己做字符串处理、大输入量题目的经验是这两句能省掉九成以上的IO性能焦虑。3.2 当cin还不够快时手写快读的两种常见姿势如果你做的是P或U开头的大数据题有时候关了同步也不够这时候就需要手写快读。常见的思路是把字符读入到缓冲区然后用getchar按字符解析出数字。给你一个我常用的整数快读模板int read() { int x 0, f 1; char c getchar(); while (c 0 || c 9) { if (c -) f -1; c getchar(); } while (c 0 c 9) { x x * 10 c - 0; c getchar(); } return x * f; }实际上getchar本身已经带缓冲区了这个写法在很多场景下不需要再套fread。对于“询问学号”这道题而言用快读属于杀鸡用牛刀但理解快读的解析逻辑对理解字符输入很有帮助建议至少抄一遍、跑一遍。3.3 输出优化\n与puts的取舍很多新手以为输出优化不重要直到遇到m大到一定程度的题。如果单条输出只是“一个整数换行”用printf(%d\n, a[q])或者直接上cout都可以。刚才说了不要用endl还有一个更快的选择是用putchar配合输出缓冲区。不过我得说句实在话在P3156这种题上你只要别用endl老老实实\n速度上就绝对没压力。“把速度意识培养起来”比“每道题都上极限优化”要重要得多。4. 常见踩坑全记录从RE、WA到TLE的完整排查链路这道题虽然简单但我亲眼看着不少新人在同一个地方栽跟头。把坑提前列出来比事后排查省时间多了。4.1 数组开小导致的RE最难发现的越界出现RE运行时错误时新手的第一反应往往是“我代码逻辑没错啊”。如果逻辑确实没问题那十有八九是数组越界。比如你开了a[1005]结果n上限是1000000读入数据时就直接写穿了。这类错误在本地测试时很难暴露因为小数据恰好能跑过等评测数据一大就崩。我不止一次遇到这种情况排查半天才发现是数组长度的问题。所以我的建议很明确全局变量数组能开多大就开多大在内存限制内宁可多开到1000005也不要卡着数据上限开。多出来的几个int对内存毫无压力但能保证你不在这种低级错误上丢分。4.2 输出格式边界换行与多空格的那些事这道题要求每次询问输出一个学号学号后面换行。有些人输出的时候习惯性地在中间加空格或者逗号例如cout a[q] ;这在有多个输出的题里是常见错误。还有人在最后习惯多打一个换行这在大多数题里没问题但个别严格判题的评测系统会认为格式错误。判断格式是否正确有个笨但有效的办法仔细看题目描述里的“输出格式”部分它会明确写每个输出之间用什么分隔。比如“询问学号”就是每行一个整数。你照着描述写别自由发挥基本不会错。4.3 读完n个学号后m次询问写进同一个循环的隐性错误还有一种典型错误是读入逻辑写得混乱导致程序先读完所有学号然后试图在同一个循环里既读学号又读询问。举个例子如果有人写成for (int i 1; i n m; i) { cin a[i]; // 实际上从第n1个开始就会读错 }数据一旦混在一起输入流就乱套了后续所有查询都会拿到错值。这种错误的特点是不崩、不报错就是答案一看就不对。排查思路是重新核对输入顺序先n再n个学号再m再m个询问。代码结构和输入顺序一一对应就不会出现这类问题。4.4 潜伏的TLE当“十万次查询”遇上“百万次遍历”如果谁真的用两层循环去做这道题比如每来一个询问q就从第1个学生找到第q个学生那么在数据上限时一定超时。这就是题目想教你的核心思想你要做的不是“每次现找”而是“提前存好要啥拿啥”。我拿生活中的例子类比一下想象一个大旅馆有n个房间每个房间门上贴着房号。如果客人每次来都问“第10个房间号是什么”你不需要每次从第1间开始一间一间数过去你在入住单上早就记好了。数组就是那张入住单输入学号的循环就是登记的过程之后每一次查询就是翻单子O(1)时间就能找到。5. 从这一题延伸到竞赛思维与工程习惯“询问学号”本身是个入门题但你如果只把它当入门题做一遍就过那有点可惜。这题背后有几个可迁移的东西值得展开讲。5.1 预处理思想的首次登场这道题是全球几乎所有算法竞赛入门者都会接触的“在线查询”问题。它的模型可以抽象为先给定一批静态数据然后有大量查询每次查询只取其中一个位置或区间。如果纯暴力每次都重新访问复杂度会随数据量和查询量相乘增长而预处理数据结构则是把构建结构的一次性成本沉下去让每次查询都接近O(1)。这个思想在后续阶段会反复出现例如前缀和、哈希表、ST表、线段树等本质上都是在“用预处理换查询时间”。P3156就是第一步预处理就是把学号放进数组查询就是按下标取简单得几乎没有存在感。但如果你能在做这道题时就形成“数据预处理”的自觉后面学前缀和、差分会轻松很多因为它们一模一样只是预处理的内容变复杂了一点。5.2 读入顺序、命名习惯与调试技巧一道入门题还能帮你养成一个习惯变量的命名和读入顺序可以一一对应。比如我习惯把数组叫a读入的计数变量叫n询问数叫m查询的序号叫q。虽然短变量名在竞赛里很常见但如果你能稍微有语义地命名比如用stuNo、query在查错时会清楚得多。另外调试这种简单题也有技巧。如果AC不了不要干瞪眼看代码直接在本地加几行中间输出看看数组前几个值是不是预期学号。如果a[1]存的不是第一个学号问题大概率出在读入逻辑如果a[q]输出不对问题大概率出在下标转换。把排查范围缩到越小错误越容易暴露。5.3 边界情况的自我拷问最后给你一个自测清单这题过了边界测试基本就稳了n1时数组只有1个元素下标1还能不能用能因为你从a[1]开始存。询问的q是否可能等于0按题目语义不会但如果你下标从0开始就有可能出现“第0个学生”的尴尬所以要留意题目的计数起点。m很大时输出缓冲问题是否处理了换行是否用了\n学号本身是否为0如果学号可以是0而你用数组初始值0来判断是否存过数据就会出问题。好在题目不会这么考但做其他题时要警惕。这些边界思考在做其他入门题时也同样适用甚至越早形成习惯越好。5.4 从数组到哈希再到树形结构一道题的引申路径如果你愿意还可以在AC之后做个小实验把数据范围扩大到1e7或者把学号变成字符串比如带字母的座位号你会发现纯数组就不够了。这时就要引入map/unordered_map或者自己写哈希。如果再把问题升级成“多次询问一段区间内的学号最大值”你就得学ST表或线段树。这其实是很好的自学路径每次在简单题AC之后问自己一句“如果数据范围再大一个数量级会怎么做”然后沿着这条线去查、去学、去试。很多后来被认为很难的知识点都是用这种“渐进式升级”的方式啃下来的。我自己当时做完这题后顺手去做了“询问区间和”的同类题从而接触到了前缀和。那时候还不知道这个名词但已经隐约感觉到“查表比现算快”的道理。回头看正是无数个这样的小小转折把朴素的直觉慢慢培养成了系统的竞赛思维。最后再分享一个关于这道题的个人体会如果你想验证自己是不是真会了不要只AC一次就换题。试着把输入输出方式从cin改成scanf、把它从数组改成vector、再把它从下标1改成下标0每个版本都跑一遍。折腾完这一圈你对“输入输出机制”“数组本质”“下标语义”这三件事的理解会明显上一个大台阶。很多人到后面遇到难题卡壳回头想想根子往往就出在入门时对这些基础细节的掌握不够瓷实。这题正好是个练手的好机会成本低收益却不小。