先说结论这题能卡住的只有 IO。“4.基础IO”这个标题看着简单实际上是把一整类经典问题浓缩成了四个字——读进去、算出来、写出来。禾木省电这道题传统题来源 tomanderson1000ms256MB就是一个非常典型的练习样本一排灯泡编号 1~n每天晚上全亮省电时给两个区间把区间内包括端点的灯泡全关掉问你最后还有哪些亮着。算法上你甚至可以说它没有算法真正要命的是把输入输出处理干净。如果你刚开始刷 OJ或者总在“看起来不难”的题上 WA这篇就是为你准备的。我会把这题完整拆开怎么理解输入、怎么写输出、哪些边界条件容易翻车、数据大了怎么优化 IO顺带给出三种由浅入深的写法。老手可以跳过前面直接看第 4 节的排查表和差分数组写法。1. 题目拆解省电灯泡题到底在考什么1.1 一次 IO 操作的完整链路先建立一个整体认知。OJ 上任何一道题程序运行时都只有两条数据通道标准输入 stdin 和标准输出 stdout。评测系统把你的程序编译好、跑起来把预先写好的测试数据喂到 stdin 里再把你写到 stdout 的内容抓出来跟标准答案做逐字节比对。比对一致就是 Accepted任何一点差异都是 Wrong Answer。这个链路决定了 IO 必须精确。你可以把 IO 理解成填答题卡规矩是每一道题都要在指定区域涂黑你哪怕全部算对了有个空格没对齐、多打了个换行照样按格式错误处理。很多新手第一次 WA 不是算法错了而是输入读取姿势不对或输出格式有偏差。这一点在“基础IO”这一课里被特意放大了所以别看它名字朴素含金量不低。1.2 输入格式里的隐藏信息回到题目。输入共三行第一行是一个整数 n表示灯泡数量第二行、第三行各是两个整数表示两个区间的左右端点。表面上看就是读 5 个整数但题目措辞里藏着几处需要留意的细节。第一灯泡编号从 1 开始不是从 0 开始。数组下标要和灯泡编号对齐要么开 n1 个元素要么在代码里做偏移。第二区间“包括端点”意味着 l 和 r 这两个位置都要被关掉循环条件是小于等于不是小于。第三题目描述没有明确保证 l 一定小于等于 r你自己的代码要做好防御读进来之后如果 l r 就交换否则循环一次都不会执行结果悄悄出错。第四n 的上限没有直接给但时间限制 1000ms、内存 256MB 已经暗示了量级在 10^5 到 10^6 这个范围内直接开布尔数组标记完全可行如果 n 到了 10^7数组定义就要小心内存输出量也会变大这是后话。1.3 算法不是主角IO 才是这道题如果只谈逻辑一句话就能说完把所有灯泡标记为亮把两个区间内的标记为灭输出还是亮的编号。区间标记本身是 O(r-l1) 的遍历两个区间加在一起最坏情况也就是 O(n)1000ms 的时限绰绰有余。所以它被排在“基础IO”这个位置目的就是让你把所有注意力放在读写环节。我见过不少人提交这道题逻辑写得完全正确结果要么是 scanf 没读够参数导致输出为空要么是输出末尾多了一个空格被比对判 WA要么是没有处理“没有任何灯泡亮着”的特殊情况。这些都是 IO 问题不是算法问题。把 IO 这一关过了这道题才算真正拿下。2. 核心细节读入、标记与输出的实现要点2.1 三行输入的正确读取姿势读取 5 个整数的方案有很多不同语言的写法差异不小我按常用性列个对比。C 语言里最稳的是 scanf。scanf(%d, n) 会自动跳过空白字符空格、换行、制表符所以你不用关心数字是在一行还是跨行。第二、第三行可以分别写两个 scanf(%d%d)也可以合并成一个 scanf(%d%d%d%d, l1, r1, l2, r2)效果一样。C 用 cin 也完全可以但注意 cin 默认和 C 的 stdio 保持同步这会拖慢速度在 main 开头加一句 ios::sync_with_stdio(false); cin.tie(0); 能明显提速。对这道题来说数据量不大普通 cin 也够用但习惯要早养。Python 的话最省事的是逐行 input() 再 split例如 n int(input())然后 l1, r1 map(int, input().split())。但如果数据量变大或者你后面要刷大量输入输出的题我建议直接 sys.stdin.read().split()一次把全部内容读进来再切片处理速度比多次 input() 快得多。这个习惯早点养成后面遇到输出很大的题不用临时换方案。语言推荐读法备注Cscanf(%d, x)自动跳过空白字符最稳健Ccin 关闭同步ios::sync_with_stdio(false); cin.tie(0);Pythonsys.stdin.read().split()大批量数据时性能优势明显2.2 区间端点与边界条件的处理处理区间有两个绕不开的细节包括端点和可能的逆序。包括端点用循环写就是 for (int i l; i r; i)下标 i 从 l 一直走到 r两个端点的灯泡都被标记为关闭。很多人写成 i r结果右端点没关掉样例可能刚好没覆盖到这个错误提交就 WA。另一个细节是逆序如果输入给了 l7, r3按 lr 的循环去写循环一次都不会执行。稳妥的做法是读进来之后先判断如果 l r 就交换两者。还有防御性处理是越界如果 r 大于 n循环会访问到数组不存在的下标轻则读到脏数据重则段错误。题目一般保证数据合法但你把 r 和 n 做一次 min 运算、把 l 和 1 做一次 max 运算成本几乎为零换来的是更稳健的代码。另外两个区间可能有重叠。布尔标记是幂等的已经关掉的灯泡再关一次状态不变。所以哪怕两个区间完全重叠也不需要额外判断直接遍历标记即可。若是用差分数组统计覆盖次数重叠也只是把次数累加并不影响“次数为 0 才是亮着”的判定。2.3 输出格式空格、换行与空结果输出是所有仍然亮着的灯泡编号按从小到大用空格分隔。这里最常见的翻车点就是分隔符的位置。很多人习惯先输出第一个再在后面的每个数字前加空格这样末尾不会有多余空格。写成代码就是一个 bool first 变量第一个数字前什么都不打之后的数字前打一个空格。末尾的换行和空格同样重要。评测比对一般是逐字节的有些评测系统允许行尾多一个空格但有些严格比对会直接判 WA。你不该赌这个规范写法就按“数字之间单空格、行尾一个换行”来。多组样例的情况下每个样例输出之后都要换行否则下一个样例的输出会紧跟在上一个末尾这种错误在终端上看很难发现。再一个特殊情况如果所有灯泡都关了输出什么有的题目要求输出 0有的要求输出一个空行有的直接不要求输出。这道题描述没写清楚建议先看样例样例没给就输出一个换行绝大多数评测系统能接受空输出。这种“空结果”的边界恰恰是基础 IO 题喜欢埋的坑。3. 三种解法由浅入深从暴力到差分数组3.1 第一版布尔数组直接标记先给一个最直白的写法。用一个长度为 n1 的布尔数组记录灯泡状态初始全部为真两个区间逐一遍历置为假最后扫描一遍输出仍为真的下标。#include cstdio const int MAXN 1000005; bool on[MAXN]; int main() { int n, l1, r1, l2, r2; scanf(%d, n); scanf(%d%d%d%d, l1, r1, l2, r2); if (l1 r1) { int t l1; l1 r1; r1 t; } if (l2 r2) { int t l2; l2 r2; r2 t; } for (int i 1; i n; i) on[i] true; for (int i l1; i r1; i) on[i] false; for (int i l2; i r2; i) on[i] false; bool first true; for (int i 1; i n; i) { if (on[i]) { if (!first) putchar( ); printf(%d, i); first false; } } putchar(\n); return 0; }拿一组小数据验证n 10两个区间是 [2,5] 和 [7,9]。初始 10 个灯泡全亮关掉 2、3、4、5再关掉 7、8、9剩下 1、6、10。程序输出 1 6 10符合预期。注意我没有用数组下标 0灯泡 1 对应 on[1]这样编号和下标直接对齐不容易乱。整个流程就是“读入—标记—输出”三步没有任何多余的技巧。3.2 第二版通用循环读取与快速输出第一版按“两行区间”写死了。但题目里那句“经过两轮操作”让不少人犯迷糊到底是两个区间一共一轮还是每轮两个区间、一共两轮与其纠结不如写一个通用的版本用 while (scanf(%d%d, l, r) 2) 持续读取区间读到文件末尾为止这样无论题目给两个区间还是四个区间代码都不用改。这个模式本身就是基础 IO 的重要技能处理不固定数量的数据。#include cstdio const int MAXN 1000005; bool on[MAXN]; int main() { int n, l, r; scanf(%d, n); for (int i 1; i n; i) on[i] true; while (scanf(%d%d, l, r) 2) { if (l r) { int t l; l r; r t; } for (int i l; i r; i) on[i] false; } bool first true; for (int i 1; i n; i) { if (on[i]) { if (!first) putchar( ); printf(%d, i); first false; } } putchar(\n); return 0; }输出部分我特意用了 putchar 处理空格、printf 输出数字避免构造一个复杂的格式化字符串。这种方法在处理大量输出时性能也不错因为 putchar 会在标准库内部做缓冲不会每个字节都触发一次系统调用。Python 对应的写法是 sys.stdin.read() 一次性读取、split 之后按对消费最后用 .join 拼输出字符串同样是一句话就能讲完的思想减少 IO 次数。import sys def solve(): data sys.stdin.read().split() if not data: return n int(data[0]) on [True] * (n 1) idx 1 while idx 1 len(data): l int(data[idx]) r int(data[idx 1]) idx 2 if l r: l, r r, l for i in range(l, r 1): on[i] False ans [str(i) for i in range(1, n 1) if on[i]] sys.stdout.write( .join(ans) \n) if __name__ __main__: solve()这个 Python 版本有个细节data 为空时直接 return避免下标越界。判断读入是否成功、处理 EOF是 IO 代码健壮性的第一步。3.3 第三版差分数组一劳永逸虽然这道题用暴力标记就够但如果你接着刷“区间操作”类的题目差分数组是绕不开的。它的核心思想是不在每个区间上做 O(len) 的逐点标记而是只在区间的起点和终点后各做一次 O(1) 的记号最后统一做前缀和还原每个位置的覆盖次数。具体到这道题开一个 diff 数组初始全 0。对每个区间 [l, r]执行 diff[l] 1 和 diff[r1] - 1表示从 l 开始多覆盖一次、从 r1 开始少覆盖一次。处理完全部区间后从 1 到 n 做一遍前缀和 diff[i] diff[i-1]diff[i] 就是第 i 个灯泡被覆盖的次数。次数为 0 的灯泡就是从头到尾没被关过输出它。#include cstdio const int MAXN 1000005; int diff[MAXN]; int main() { int n, l, r; scanf(%d, n); while (scanf(%d%d, l, r) 2) { if (l r) { int t l; l r; r t; } diff[l] 1; diff[r 1] - 1; } bool first true; for (int i 1; i n; i) { diff[i] diff[i - 1]; if (diff[i] 0) { if (!first) putchar( ); printf(%d, i); first false; } } putchar(\n); return 0; }注意 diff 数组要开 n2 个元素因为当 r 等于 n 时r1 是 n1这个位置也要能写。整个算法复杂度是 O(nm)m 是区间个数。对两个区间来说它和暴力没差别但当你面对成千上万个区间时这就是质变。从“基础IO”这道题里顺手学会它属于典型的以小见大。4. 常见问题与排查技巧实录4.1 读入失败、越界与端点乱序的处理我实际帮人调试这道题时遇到最多的一个症状是程序没有任何输出或者只输出了一个换行。多数情况下是 scanf 没读进来。比如有人用 scanf(%d, n) 忘了取地址符或者读入时把 n 和第二行的 l 混在一起。C 语言里这种错误编译器不一定报错但程序行为完全不对。第二个高频症状是段错误。常见原因是数组开小了或者 r 超出了 n。比如 n1000但区间给到 [999, 1500]循环访问 on[1500] 时越界。防御写法是把区间裁到合法范围内l max(l, 1)r min(r, n)。第三个症状比较隐蔽l 大于 r。如果你不做交换循环体一次都不执行你以为区间关了其实没关。这也是为什么我在所有代码里都先写 if (l r) swap这个习惯能帮你挡掉不少莫名其妙的数据。4.2 输出格式错误WA 的隐形杀手最气人的情况是本地跑得一丝不差提交却 WA。遇到这种先把矛头指向输出格式。我建议在本地做一次字节级比对把程序输出重定向到文件再用 diff 和标准答案做对比如果有差异用 od -c 或 cat -A 查看不可见字符的区别。常见差异有三类末尾多空格、末尾没有换行、把编号从 0 开始输出。第一类多是因为用循环 printf(%d , i) 的结果最后一轮多打了一个空格。第二类多是因为忘了在输出结束后补换行。第三类多是因为初始化数组时不小心从 0 开始循环输出下标而不是编号。这些差异肉眼看不出来但评测系统能看出来。4.3 1000ms 下的 IO 性能优化实录这道题数据量不大但既然时限写的是 1000ms我就把 IO 性能的账也算一遍。最慢的写法是每一个输出都调用一次 printf 或 cout尤其 cout 没关同步时每输出一个数字就抢一次锁性能非常难看。快一点的做法是拼字符串C 里用 string 把所有答案拼好最后 cout 一次C 里可以用 sprintf 拼到缓冲区或者用 putchar 逐字符写。再快一档是自制的快速读入。用 getchar 逐个字符读取并转为整数对 10^5 量级的输入来说收益不大但如果 n 到 10^7输入输出都以百万计快读和批量输出能省下可观的时间。我贴一个常用的整数快读模板C/C 通用int readint() { 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; }这里处理了负号虽然本题用不到负数但后续很多题都会用到负数输入直接复制这个模板能省很多事。我的经验是基础 IO 题老老实实用 scanf 就够但把快读模板存进自己的代码仓库遇到大输入量的题直接拿来用能少走很多弯路。4.4 常见问题速查表现象可能原因解决办法运行无输出读入失败或参数错误检查 scanf 参数、数据文件是否为空段错误数组越界扩大数组、对 r 做 min(r, n)、diff 开 n2输出末尾多空格循环输出每个数字后跟空格用 first 变量控制分隔符输出缺少换行忘记补行尾换行输出结束后 putchar(\n)逻辑对但结果错区间端点写错、lr 未处理检查循环等号、增加交换保护大样例超时输出次数过多拼接输出、批量 fwrite输出空但应该有内容读取循环没有正确处理 EOFwhile(scanf)2 判断返回值这张表可以直接贴在你刷题笔记的第一页。每次遇到 WA先按表排查再看算法效率会高很多。5. 从竞赛 IO 到工程 IO能力迁移5.1 同一个 IO 内核在不同领域的映射如果你搜过“IO”这个词会发现它在不同语境下有完全不同的含义Java IO 指的是输入输出流PLC 里的远程 IO 模块指的是现场设备的数据采集通道FPGA 里的 IO 约束指的是引脚和时钟资源的分配模拟工厂场景的 Factory IO 又是指一套仿真通信框架。词义很多但你钻进每个领域细看底层都逃不过三件事接口协议、边界处理、性能控制。竞赛里的 scanf 对应的是“我知道评测系统按什么格式喂我我就按什么格式读”FPGA 的 IO 约束对应的是“我知道引脚连接什么电平标准就按那个标准约束时序”PLC 的 IO 模块对应的是“我知道总线周期和从站地址就按那个协议采集数据”。这套思维是可以迁移的先把通信双方的约定吃透再把边界情况想全最后才谈吞吐量。这道看似幼稚的灯泡题炼的其实是这套通用直觉。5.2 培养 IO 直觉的三个习惯根据我自己的经验IO 能力的提升靠三个习惯。第一拿到任何题先花十秒钟画一遍输入样例和输出样式的草图把“空结果”“边界值”“多组数据”这三种情况在脑海里跑一遍。第二提交前自测三个用例最小数据n1、最大数据按题目上限构造、以及什么都不剩的情况。第三把自己常用的读取、输出、快读模板整理成固定工具不断复用而不是每次现写。这三个习惯在竞赛里帮我省了大量调试时间后来做工程开发时也一样受用。比如对接外部接口时我习惯先确认报文格式和空值情况再写业务逻辑这跟先把输入输出格式抠清楚的思路完全一致。说白了IO 是程序和世界之间唯一的两扇门你对这两扇门有多熟悉决定了你的程序在外人眼里是可靠还是靠运气。最后再分享一点个人体会。我早期刷题时最怕的不是难题而是那种“明明全对了却 WA”的诡异感后来发现十次里有八次是 IO 的问题要么多空格要么少换行要么读入时下标错位。这道基础 IO 的灯泡题让我彻底改了习惯从此所有输出都先重定向到文件做 diff再提交。这个习惯到现在还在用也推荐给你。