记录136#includebits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n,a1,b1; //n次变动 a是分子b是分母 bool f1; // 到边界后true向右边走 false向下走 cinn; //输入n nn-1; //第一次已经在1/1位置了所以实际移动n-1次 while(n--){ //开始移动 if(a1f){ //到最上面了向右走 b,f0; //向右走一格后面到边界向下走 }else if(b!1!f){ //没走到最左边并且到边界是向下走 a,b--; // 到当前位置的左下位置 }else if(b1!f){ //到最左边了 向下走 a,f1; //向下走后面到边界向右走 }else if(a!1f){ //没走到最上面并且到边界是向右走 a--,b; //到当前位置的右上位置 } } couta/b\n;//输出 return 0;//程序正常结束 }题目传送门https://www.luogu.com.cn/problem/P1014前言我是一名专注信奥赛CSP-J/S、NOIP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道经典的找规律与模拟问题。题目要求我们按照“Z字形”遍历一个无限的有理数表并输出第 N 项。观察 Z 字形规律我们将有理数表看作一个二维坐标系分子a代表行分母b代表列。观察题目给出的遍历顺序1/1(起点)1/2(向右移动)2/1(向左下移动)3/1(向下移动)2/2(向右上移动)1/3(向右上移动)1/4(向右移动)...我们可以发现移动轨迹只有四种基本状态向右平移当处于第一行且当前方向是向右上时只能向右走一格然后方向变为向左下。向左下斜移只要不在第一列且方向是向左下就不断向a1, b-1移动。向下平移当处于第一列且当前方向是向左下时只能向下走一格然后方向变为向右上。向右上斜移只要不在第一行且方向是向右上就不断向a-1, b1移动。模拟算法设计由于N最大为 10^7使用 O(N) 的循环模拟是可以接受的。我们只需要设置两个变量a分子和b分母以及一个布尔变量f来记录当前是在“向右上走”还是“向左下走”按照上述四种情况逐步移动N-1次即可得到结果。代码分块详细解释1. 头文件、变量定义与初始化#includebits/stdc.h using namespace std; int main(){ ios::sync_with_stdio(false); // 关闭标准流同步提升输入输出效率 cin.tie(0); // 解除cin与cout的绑定加快读取速度 int n, a1, b1; // n次变动a是分子b是分母 bool f1; // 到边界后true代表向右边走向右上false代表向下走向左下详细分析这里定义了核心的状态变量。a和b初始化为 1代表起点1/1。布尔变量f是控制移动方向的关键标志位。f1(true) 表示当前的斜线方向是向右上分子减小分母增大f0(false) 表示当前的斜线方向是向左下分子增大分母减小。2. 输入处理与步数修正cinn; // 输入n nn-1; // 第一次已经在1/1位置了所以实际移动n-1次详细分析因为我们的起点a1, b1已经对应了第 1 项所以如果要求第 N 项实际上只需要在起点的基础上再移动N-1步。这一步处理避免了循环多执行一次。3. 核心循环Z字形移动模拟while(n--){ // 开始移动循环执行 n-1 次 if(a1 f){ // 到最上面了向右走 b, f0; // 向右走一格分母1后面到边界向下走方向变为向左下 } else if(b!1 !f){ // 没走到最左边并且到边界是向下走 a, b--; // 到当前位置的左下位置分子1分母-1 } else if(b1 !f){ // 到最左边了 向下走 a, f1; // 向下走分子1后面到边界向右走方向变为向右上 } else if(a!1 f){ // 没走到最上面并且到边界是向右走 a--, b; // 到当前位置的右上位置分子-1分母1 } }详细分析这是代码的灵魂部分利用if-else if结构完美覆盖了四种移动状态。状态 1右上角边界a1 f。当我们在第一行且原本打算向右上走时会被边界挡住此时只能向右平移一格b并且将方向f翻转为0准备向左下走。状态 2向左下斜移b!1 !f。只要不在第一列b!1且方向是向左下!f就沿着对角线向左下移动a, b--。状态 3左下角边界b1 !f。当我们在第一列且原本打算向左下走时会被边界挡住此时只能向下平移一格a并且将方向f翻转为1准备向右上走。状态 4向右上斜移a!1 f。只要不在第一行a!1且方向是向右上f就沿着对角线向右上移动a--, b。4. 结果输出couta/b\n; // 输出 return 0; // 程序正常结束 }详细分析循环结束后a和b中存储的就是第 N 项对应的分子和分母按照题目要求的格式输出即可。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点状态初始化a1, b1, f1设定起点与初始方向确立了模拟的基准状态f1代表初始趋势向右上步数修正n n - 1排除起点占用的第1项避免循环多执行一次确保移动次数准确右上边界处理if(a1 f)处理第一行的向右平移解决向右上移动碰到顶墙时的转向与平移问题左下边界处理else if(b1 !f)处理第一列的向下平移解决向左下移动碰到左墙时的转向与平移问题对角线移动a,b--与a--,b实现Z字形的斜向遍历在两个边界之间来回穿梭完美复刻康托尔表的规律方向翻转f0与f1切换斜线移动的方向保证每次碰到边界后下一次斜移的方向必然改变