当前位置:首页 > 入门组 > 2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析

2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析

3天前

2023年CSP-J 小苹果题解(洛谷P9748) | 动态规划解题思路与代码解析 CSP-J 洛谷P9748 小苹果题解 动态规划 数学推导 第1张

一、题目解读

CSP-J 2023年的小苹果题目(对应洛谷P9748)是一个经典的动态规划问题。题目描述了一个苹果被依次取走的场景:每天取走当前苹果数量的 (n-1)/3 + 1 个苹果,直至全部取完。需要计算两个关键值:总天数和最后一个苹果被取走的天数。该题目考验对循环规律的观察与数学推导能力,需通过编程实现高效的解题逻辑。

二、解题思路

作者提供的代码采用循环模拟与标记法解决该问题。核心思路为:

1. 天数递增与取苹果逻辑:通过循环模拟每天的操作,每次计算取走的苹果数为 (n-1)/3 + 1。

2. 关键节点标记:当剩余苹果数满足 (n-1) % 3 == 0 时,说明当前轮次取走最后一个苹果,记录天数。

3. 动态更新剩余苹果数:通过数学推导优化,避免直接模拟取苹果过程,提升效率。

三、解题步骤解析

1. 初始化变量:

    n 为苹果总数,days 初始化为0,last_day 记录关键天数,found 标记是否找到目标苹果。

2. 循环模拟取苹果过程:

    每天 (days++) 计算取走数量 (n-1)/3 + 1,更新剩余苹果数 n -=...。

3. 判断关键节点:

    当 n-1 为3的倍数时,说明当前取走最后一个苹果,记录天数并标记 found。

4. 终止条件:当 n=0 时,循环结束,输出总天数和关键天数。

四、代码与注释

#include <iostream>  
using namespace std;  

int main() {  
    int n; // 苹果总数  
    cin >> n;  
    int days = 0; // 总天数  
    int last_day = 0; // 第n个苹果被取走的天数  
    bool found = false; // 是否已找到第n个苹果  
    
    while (n > 0) {  
        days++; // 天数增加  
        // 检查当前轮次是否取走第n个苹果  
        if (!found && (n - 1) % 3 == 0) {  
            last_day = days;  
            found = true;  
        }  
        // 计算本轮取走的苹果数:(n-1)/3 + 1  
        n -= ((n - 1) / 3 + 1);  
    }  
    
    cout << days << " " << last_day << endl;  
    return 0;  
}

注释说明:代码通过循环与条件判断,结合数学推导简化计算,高效求解目标天数。

五、总结

该题目通过动态规划思想,将复杂模拟转化为数学逻辑推导。关键点在于识别取苹果的规律(每轮取走 (n-1)/3 + 1 个)和标记最后一个苹果的位置。代码简洁且时间复杂度低,适合竞赛场景。掌握此类问题的解题思路,有助于提升对循环规律与数学优化的理解。


原创内容 转载请注明出处

分享给朋友:

相关文章

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

IOI 1994 洛谷1216:如何用动态规划高效解决数字三角形问题?附完整代码解析

题目重解给定一个由数字组成的三角形结构,从顶部出发,每次可以移动到下方相邻的数字,最终到达底部。我们的目标是找到一条路径,使得路径上经过的数字总和最大。这个问题在实际中有许多应用场景,如最优路径规划、...

GESP2023年六级真题解析:动态规划解决小杨买饮料问题(洛谷3873)

GESP2023年六级真题解析:动态规划解决小杨买饮料问题(洛谷3873)

一、题目解读小杨买饮料是GESP 2023年六级认证考试中的一道经典动态规划题目,考察学生对背包问题的理解和应用能力。题目描述小杨需要购买n种饮料,每种饮料有特定的体积w和价格v,他要在不超过容量l的...

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

牛客12576题解题全解析:动态规划+质因数分解实现跳跃问题最优解

一、题目解读牛客12576题是一道经典的算法题,要求给定起点N和终点M,求解从N到M的最少跳跃次数。题目考察的核心在于路径优化与动态规划思想,需结合数论中的质因数分解技巧,通过合理设计算法降低时间复杂...

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

CSP-J 2019公交换乘题解析:基于队列优化的动态规划代码详解

一、题目解读CSP-J 2019年的“公交换乘”题目(洛谷P5661)要求模拟地铁与公交交替出行的费用计算。题目核心在于地铁消费会产生优惠券,而公交可在45分钟内使用优惠券抵扣车费。需要处理n条出行记...

洛谷2789题解:直线交点数的递归求解与优化(附代码详解)

洛谷2789题解:直线交点数的递归求解与优化(附代码详解)

一、题目解读洛谷2789题要求计算n条直线在平面上两两相交时产生的不同交点数量。题目强调“不同”交点,需排除重复情况。解题关键在于如何高效枚举所有可能的交点组合,并避免重复计数。二、解题思路参考代码采...

洛谷P4999题解析:动态规划求解数字拆分与求和问题(附代码)

洛谷P4999题解析:动态规划求解数字拆分与求和问题(附代码)

一、题目解读洛谷P4999题要求处理给定区间 [L, R] 内数字的拆分与求和问题。每个数字需拆分为其各位数字之和,并计算区间内所有数字之和的累加结果。题目需考虑大数情况,并采用取模运算(MOD=1e...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。