记录一道 GESP 2023年12月 的二分真题。这类题在考试里属于必得分项核心就那几行代码关键是别在小细节上丢分。题目来源ACGO A95154 2023年12月 五级赛事场次2023年12月 五级一、题目信息题目名称小杨的幸运数赛事场次2023年12月 五级难度定位五级涉及知识点二分答案 筛法题目链接https://www.acgo.cn/problemset/info/95154坑点这题失分基本都在这答案的单调性判定判定函数的写法。题意简述小杨认为所有大于等于 a 的完全平方数都是他的超级幸运数。小杨还认为所有超级幸运数的倍数都是他的幸运数。自然地小杨的所有超级幸运数也都是幸运数。对于一个非幸运数小杨规定可以将它一直 1直到它变成一个幸运数。我们把这个过程叫做幸运化。例如如果 a4那么 4 是最小的幸运数而 1不是但我们可以连续对 1 做 3 次 1 操作使其变为 4所以我们可以说1 幸运化后的结果是 4。现在小杨给出 N 个数请你首先判断它们是不是幸运数接着对于非幸运数请你将它们幸运化。前置知识这道题用到的前置知识不多我们先把它补齐即使你刚学到这里也能看懂。读懂题意先把题目要求的输入输出格式看清楚明确我们要算什么、按什么格式输出这是所有题的第一步。二、思路分析先看清楚题目要我们做什么把题目读两遍我们提取出关键信息输入是什么、要输出什么、有哪些约束条件。这道题考查的是二分属于这类题里比较基础的一道把题目要求一步步翻译成代码逻辑就能解决。我的思考过程读完题之后我的第一反应是这样的1 . 预处理程序通过预处理计算出所有小于等于 N 的幸运数。这里使用了一个布尔数组 is _ lucky 来标记每个数是否是幸运数以及一个数组 next _ lucky 记录每个位置之后的下一个幸运数。顺着这个方向往下想就得到完整做法2 . 循环通过两个嵌套的循环对每个数进行判断和幸运化。外层循环遍历给定的数内层循环用来标记倍数。3 . 判断和输出根据预处理得到的 is _ lucky 数组对于每个给定的数判断它是否是幸运数。如果是输出 lucky 否则输出该数之后的下一个幸运数。4 . 主函数在主函数中首先读取输入的 a 和 N 然后进行预处理接着循环处理每个给定的数输出结果。这段代码的目的是判断给定的数是否是幸运数如果不是则输出该数之后的下一个幸运数。该算法的核心思想是通过预处理得到幸运数的信息以提高对给定数的判断效率。需要说明的是上面这个思路是把题目要求直译成代码得到的没有用到什么高级技巧。对于这类基础题读准题意加写对边界比追求巧妙解法更重要因为考试里这种题是必须拿满分的。三、完整代码 逐行注释#include cstdio #include cstdlib #include cstring #include algorithm #include string #include map #include iostream #include cmath using namespace std; const int N 1001 * 1001; const double eps 1e-8; bool is_lucky[N 5]; int next_lucky[N 5]; // 初始化函数 void init() { // 可以在这里添加一些初始化的操作 } int main() { int a, T; // 读取输入的a和T scanf(%d%d, a, T); // 预处理计算幸运数 for (int i 1; i N; i) { // 遍历 int t int(sqrt(i) eps); // 判断是否是幸运数 if (i a t * t i) // 判断 is_lucky[i] 1; // 如果不是幸运数继续下一个数 if (!is_lucky[i]) // 判断 continue; // 标记倍数 for (int j i i; j N; j i) // 遍历 is_lucky[j] 1; } // 计算每个位置之后的下一个幸运数 for (int i N; i; i--) // 遍历 next_lucky[i] is_lucky[i] ? i : next_lucky[i 1]; // 处理每个给定的数 while (T--) { int x; // 读取输入的数 scanf(%d, x); // 判断是否是幸运数输出结果 if (is_lucky[x]) // 判断 cout lucky endl; // 输出 else cout next_lucky[x] endl; // 输出 } return 0; }四、代码分段拆解为了看得更清楚我们把代码按功能分成几段解释。第一步引入头文件#include cstdio #include cstdlib #include cstring #include algorithm #include string #include map #include iostream #include cmath using namespace std;#include iostream提供输入输出功能using namespace std;让我们能直接写cin、cout而不用加前缀。这两行是几乎所有 C 程序的开头照写即可。第二步读入数据scanf(%d%d, a, T); scanf(%d, x);注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用long long。第三步核心处理逻辑for (int i 1; i N; i) { for (int j i i; j N; j i) for (int i N; i; i--) while (T--) {这一段是整道题的关键也是二分的体现。看循环的三个要素从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错结果都会不对。第四步按要求输出cout lucky endl; cout next_lucky[x] endl;输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA这种分丢得最可惜。五、实例模拟下面用样例数据走一遍流程你能看到每一步变量是怎么变化的。以题目的第一组样例为例样例输入2 4 1 4 5 9样例输出4 lucky 8 lucky把这份输入代进代码程序会先把数据依次读入然后进入循环逐个判断把满足条件的值累积起来最后按格式输出。建议你对照着代码在纸上走一遍前两次循环确认自己对每一步的理解都和程序一致。题目另外还给了 1 组样例做完之后建议把剩下的样例都跑一遍全部通过再提交能避开大部分边界问题。六、踩坑总结下面是做这道题时最容易出错的地方对照自己的代码检查一下变量类型选错虽然本题范围不大但养成习惯——凡是不确定范围时累加变量一律用long long成本为零但能保命。取余与整除混淆a % b取的是余数a / b取的是整数商两个完全不同。判断倍数关系用a % b 0写成a / b 0就全错了。输出格式不符题目要求输出几行就输出几行行末换行、数字之间的空格都要严格对齐算法对了但格式错了同样判 WA这种分丢得最冤。特殊情况没特判把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入出题人最喜欢在这里设陷阱。七、知识点拓展这题虽然简单但背后的方法可以推广总结如下本题考查二分的基本写法这类题在考试中属于必得分项要练到能默写。写完代码后建议自己造几组边界数据测试特别是最小值和最大值。同一知识点在不同场次反复出现把这道题的写法吃透后面遇到同类题可以直接套用。八、适用人群适合正在备考 五级、想确认自己二分基础是否扎实的同学。以上就是这道题的全部内容。这个系列会按考试场次逐题更新觉得有帮助的话可以关注一下也欢迎在评论区留下你的解法。