信息学奥赛刷题实战OpenJudge NOI 1.5 31题‘开关灯’的三种避坑写法在信息学竞赛的刷题过程中OpenJudge和NOI等平台的题目往往考察的不仅是算法能力更是对细节处理的严谨性。许多选手在解决看似简单的题目时常常因为输出格式、边界条件或初始化问题而反复提交却无法AC答案正确。今天我们就以NOI 1.5的第31题开关灯为例深入剖析三种不同的解法及其常见陷阱。这道题描述了一个经典的开关灯问题有n盏灯和m个人第一个人将所有灯关闭第二个人改变所有2的倍数的灯的状态第三个人改变所有3的倍数的灯的状态依此类推。最终需要输出所有关闭的灯的编号用逗号分隔。题目看似简单但实际编码时会遇到多个需要特别注意的细节。1. 数组模拟法最直观的解法与常见错误数组模拟是最直接能想到的解法通过一个布尔数组记录每盏灯的状态然后模拟每个人的操作过程。这种方法虽然思路清晰但隐藏着几个容易出错的细节。#include bits/stdc.h using namespace std; int main() { bool a[5005] {}; // 初始化为false表示灯关闭 int n, m; cin n m; for (int i 2; i m; i) { // 从第二个人开始 for (int j 1; j n; j) { if (j % i 0) { a[j] !a[j]; // 简洁的状态翻转写法 } } } bool isFirst true; for (int j 1; j n; j) { if (!a[j]) { if (!isFirst) cout ,; cout j; isFirst false; } } return 0; }常见错误点数组初始化问题题目说明第一个人将所有灯关闭因此数组应初始化为false。有些选手会错误地初始化为true。循环起始值错误第一个人的操作已经体现在初始化中循环应从第二个人开始(i2)但不少选手会错误地从i1开始。输出格式问题最后一个数字后面不能有逗号这需要使用标志位(isFirst)来控制。直接在每个数字后加逗号会导致格式错误。数组下标问题题目中灯编号从1开始但有些选手习惯性地从0开始导致逻辑错误。提示使用a[j] !a[j]可以简洁地实现状态翻转比if-else判断更优雅且不易出错。2. 因数统计法数学思维的巧妙应用第二种解法跳出了模拟过程的思维定式从数学角度分析每盏灯最终的状态。这种方法效率更高但理解起来需要一些数学思维。核心思路每盏灯的最终状态取决于它被操作次数的奇偶性。初始状态为开奇数次操作后灯关闭偶数次操作后灯打开。而一盏灯被操作的次数等于它的因数个数人编号是灯编号的因数。#include bits/stdc.h using namespace std; int main() { int n, m; cin n m; cout 1; // 1号灯只有一个因数1必定关闭 for (int i 2; i n; i) { int factorCount 0; for (int j 1; j m; j) { if (i % j 0) factorCount; } if (factorCount % 2 1) { cout , i; } } return 0; }优化点分析减少不必要的计算1号灯必定关闭可以直接输出减少一次循环计算。因数判断范围对于灯i只需要检查1到min(i,m)的数字是否为因数可以进一步优化循环次数。数学性质利用完全平方数有奇数个因数非完全平方数有偶数个因数。可以利用这一性质进一步优化算法。常见错误因数统计范围错误有些选手会错误地统计1到i的所有因数而实际上只需要统计1到m的因数。初始状态处理不当忘记1号灯的特殊情况导致第一个数字前多出逗号。奇偶判断错误混淆了操作次数与最终状态的关系导致逻辑错误。3. 标志位法空间效率的极致优化第三种解法在第二种的基础上更进一步不使用数组存储所有灯的状态而是对每盏灯独立计算其最终状态大大节省了内存空间。#include bits/stdc.h using namespace std; int main() { int n, m; bool lightOn; cin n m; cout 1; // 处理1号灯 for (int i 2; i n; i) { lightOn true; // 初始为开 for (int j 1; j m; j) { if (i % j 0) { lightOn !lightOn; } } if (!lightOn) { cout , i; } } return 0; }优势对比方法时间复杂度空间复杂度适用场景数组模拟法O(mn)O(n)小规模数据易理解因数统计法O(nm)O(1)中等规模数据标志位法O(nm)O(1)大规模数据实现细节内层循环优化当j超过i/2时i%j不可能为0可以提前终止循环。输出处理与因数统计法类似1号灯单独处理避免多余的逗号。变量作用域lightOn变量在每次外层循环开始时重置确保每盏灯的判断独立。4. 调试技巧与竞赛经验分享在实际竞赛中除了写出正确的算法如何快速调试和验证代码同样重要。以下是针对这道题的一些实用调试技巧常见WA原因排查清单输出格式错误检查最后一个数字后是否有逗号确认数字之间只有一个逗号没有空格边界条件错误n1或m1时的特殊情况数组大小是否足够一般设为n5更安全逻辑错误灯编号是否从1开始状态翻转逻辑是否正确初始状态设置是否符合题意调试建议小数据测试先用n5,m3这样的小数据手动计算预期结果验证程序输出。打印中间状态在模拟过程中输出每步操作后的灯状态帮助理解程序行为。代码对比将三种解法的输出结果对比确保一致性。竞赛策略仔细阅读题目至少读两遍划出关键条件如初始状态、操作顺序、输出格式。先写伪代码理清思路再编码避免边写边改。模块化测试每完成一个功能就进行测试不要等全部写完再调试。时间分配如果一种方法调试超过20分钟仍不通过考虑换一种思路。在实际比赛中我遇到过一位选手因为输出格式中多了一个空格而WA了三次。后来他养成了专门检查输出格式的习惯甚至为此编写了输出格式检查函数。这种对细节的极致关注正是高水平选手的必备素质。
