本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P10132 [USACO24JAN] Cannonball B - 洛谷【题目描述】Bessie 已经精通了变成炮弹并沿着长度为N NN1 ≤ N ≤ 10 5 1\le N\le 10^51≤N≤105的数轴弹跳的艺术数轴上的位置从左到右编号为1 , 2 , ⋯ , N 1,2,\cdots,N1,2,⋯,N。她从某个整数位置S SS1 ≤ S ≤ N 1\le S\le N1≤S≤N开始以1 11的起始能量向右弹跳。如果 Bessie 的能量为k kk则她将弹跳至距当前位置向前距离k kk处进行下一次弹跳。从1 11到N NN的每个整数位置上均有炮击目标或跳板。每个炮击目标和跳板都有一个在0 00到N NN范围内的整数值。一个数值为v vv的跳板会使 Bessie 的能量增加v vv并反转她的方向。一个数值为v vv的炮击目标会当着陆时能量不小于v vv时被击破。着陆在炮击目标上不会改变 Bessie 的能量和方向。被击破的炮击目标将保持击破状态Bessie 依然可以该炮击目标上弹跳同样不会改变能量和方向。如果 Bessie 弹跳无限长的时间或直到她离开数轴她会击破多少个炮击目标如果 Bessie 开始时位于一个她可以击破的炮击目标她会立刻这样做。类似地如果 Bessie 开始时位于一个跳板跳板的效果将在她第一次跳跃之前生效。【输入】输入的第一行包含N NN和S SS其中N NN为数轴的长度S SS为 Bessie 的起始位置。以下N NN行描述了每一个位置。其中第i ii行包含整数q i q_iqi​和v i v_ivi​如果位置i ii上有一个跳板则q i 0 q_i0qi​0位置i ii上有一个炮击目标则q i 1 q_i1qi​1v i v_ivi​是位置i ii上的跳板或炮击目标的数值。【输出】输出一个整数为将被击破的炮击目标数量。【输入样例】5 2 0 1 1 1 1 2 0 1 1 1【输出样例】1【核心思想】问题分析Bessie 在一条长为N NN的数轴上弹跳起始位置S SS初始能量为1 11方向向右。每个位置要么是跳板q i 0 q_i0qi​0数值v i v_ivi​要么是炮击目标q i 1 q_i1qi​1阈值v i v_ivi​。Bessie 每次以当前能量k kk向前跳k kk格若落在跳板上则能量增加v i v_ivi​并反转方向若落在炮击目标上若当前能量≥ v i \ge v_i≥vi​则击破它击破后仍可停留但不再改变状态。求她能击破的炮击目标总数。由于能量和方向会不断变化可能进入无限循环或最终离开数轴。核心是模拟弹跳过程并检测循环。算法选择模拟 循环检测按规则逐步模拟 Bessie 的跳跃。关键优化是检测跳板状态的重复——因为只有跳板会改变能量和方向而炮击目标不会改变状态。若 Bessie 以相同的能量和方向再次到达同一个跳板则后续轨迹将完全重复进入无限循环此时应停止模拟不会再击破新的目标。代码中用vis和lastpower记录每个跳板是否被访问过以及当时的力量值若重复则跳出。炮击目标处理着陆在炮击目标上时若能量足够则击破计数并标记为已破将阈值设为大数但无论是否击破Bessie 的能量和方向均不变继续下一次跳跃。关键步骤读入读取N , S N, SN,S以及每个位置的类型type和数值val。初始化Bessie 状态pos Spower 1dir 1向右。cnt 0击破数tot为炮击目标总数可提前统计用于提前终止。模拟循环当pos在[ 1 , N ] [1, N][1,N]内且cnt tot时若当前位置是炮击目标若power val且尚未击破val未被设为大数则cnt并将val设为INF标记已破。位置、能量、方向不变。若当前位置是跳板循环检测若该跳板已被访问过且记录的lastpower power则说明进入重复状态跳出循环。否则记录vis 1lastpower power。方向反转dir -dir。能量增加power val。计算下一步位置pos dir * power。输出cnt。时间/空间复杂度时间复杂度O ( N 跳跃次数 ) O(N \text{跳跃次数})O(N跳跃次数)。由于每个跳板状态方向能量最多被有效访问一次重复即终止跳跃次数受限于状态数实际可行。空间复杂度O ( N ) O(N)O(N)存储每个位置的类型、数值和跳板的访问记录。模拟 循环检测的核心思想状态关键点Bessie 的状态变化只发生在跳板上炮击目标不会改变状态。因此跳板是决定轨迹是否重复的关键节点。重复判定如果 Bessie 以完全相同的能量和方向再次到达同一个跳板那么之后的所有跳跃都将与之前相同进入无限循环且不会再击破新的炮击目标。及时检测并退出可避免无限循环。炮击目标只影响计数炮击目标被击破后只是标记为“已破”不影响 Bessie 的物理状态所以无需特殊处理除了防止重复计数。适用场景适用于“状态转移由特定节点跳板改变其他节点不影响状态”的模拟问题。核心是通过记忆关键节点的状态组合来检测环。【算法标签】#普及- #模拟【代码详解】#includebits/stdc.husingnamespacestd;intn;// 房间数量ints;// 起始房间编号intcnt;// 已击败的敌人数量inttot;// 敌人总数intstep;// 移动步数用于调试或限制循环次数// 房间结构体structnode{inttype;// 房间类型0弹簧1敌人intweight;// 房间数值弹簧的弹力值/敌人的生命值intvis;// 标记弹簧是否被访问过intlastpower;// 上次访问弹簧时的力量值}p[100005];// 人物结构体structPerson{intdir;// 移动方向1向右-1向左intpower;// 当前力量值intpos;// 当前位置房间编号};intmain(){// 输入房间数量和起始位置cinns;// 输入每个房间的信息for(inti1;in;i){cinp[i].typep[i].weight;if(p[i].type1){tot;// 统计敌人总数}}// 初始化贝西的状态Person bessie{1,1,s};// 初始方向向右力量为1位置为sintflag0;// 标志变量未使用// 主循环贝西在房间之间移动while(bessie.pos1bessie.posn){// 调试用的步数限制注释掉的代码// if (step n - 1) break;// 如果已击败所有敌人退出循环if(totcnt){// flag 1;break;}// 调试输出注释掉的代码// cout pos bessie.pos endl;// cout power bessie.power endl;// 处理敌人房间type1if(p[bessie.pos].type1){// 调试输出注释掉的代码// cout 1 power bessie.power endl;// 如果力量足够击败敌人if(bessie.powerp[bessie.pos].weight){cnt;// 击败敌人计数加1p[bessie.pos].weight1e9;// 将敌人生命值设为极大值标记为已击败}}// 处理弹簧房间type0if(p[bessie.pos].type0){// 调试输出注释掉的代码// cout 0 power bessie.power endl;// 检测循环如果弹簧已被访问过且力量值相同说明进入死循环if(p[bessie.pos].vis1bessie.powerp[bessie.pos].lastpower){break;// 退出循环避免无限循环}// 改变移动方向bessie.dirbessie.dir*-1;// 标记弹簧已被访问记录当前力量值p[bessie.pos].vis1;p[bessie.pos].lastpowerbessie.power;// 增加力量值弹簧效果bessie.powerbessie.powerp[bessie.pos].weight;}// 移动到下一个位置bessie.posbessie.pos(bessie.dir*bessie.power);step;// 步数计数用于调试或循环控制}// 输出击败的敌人数量coutcntendl;return0;}【运行结果】5 2 0 1 1 1 1 2 0 1 1 1