当前位置:首页 > 入门组 > 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 个)和标记最后一个苹果的位置。代码简洁且时间复杂度低,适合竞赛场景。掌握此类问题的解题思路,有助于提升对循环规律与数学优化的理解。


原创内容 转载请注明出处

分享给朋友:

相关文章

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

2024年GESP五级武器强化(洛谷B4071)解题代码C++版

一、题目解读    2024年GESP(青少年软件编程能力等级考试)五级中的“武器强化”(洛谷平台题目编号B4071)是一道典型的算法优化问题。题目要求通过合理...

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

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

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

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

洛谷P4551题解题报告:图论与Trie树优化异或路径问题的实战解析

一、题目解读洛谷P4551题要求在一个无向图中,寻找任意两点路径权值异或后的最大值。题目输入为图的边信息(点数n和n-1条边),每条边包含起点、终点及权值。需输出所有路径中权值异或的最大值。问题核心在...

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

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

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

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

牛客25461题解析:花园喷泉距离优化算法(动态规划+后缀数组解法)

一、题目解读牛客25461题要求计算一个花园中n朵花到两个喷泉的最小距离平方和。用户需输入喷泉坐标(x1,y1)和(x2,y2),以及n朵花的坐标(x,y),通过合理分配每朵花到两个喷泉的距离,使总距...

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

LeetCode 2222题解析:高效统计"010"与"101"子序列数量的算法优化

一、题目解读题目要求计算给定字符串中包含"010"或"101"子序列的数量。关键难点在于高效遍历所有子序列,避免重复计算。传统暴力解法时间复杂度O(n^3)会超...

发表评论

访客

看不清,换一张

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