省赛练习2——第八届福建省大学生程序设计竞赛 &补题
发布日期:2021-05-14 13:34:47 浏览次数:16 分类:精选文章

本文共 1036 字,大约阅读时间需要 3 分钟。

作为一名开发人员,我最近参加了一些编程比赛,写了两道关于大数类运算的题目。特别是Problem 2278 YYS和Problem 2281 Trades这两道题,让我有些头疼。让我在这里分享一下我的思考过程。

首先是Problem 2278iskeyYY的开发历程。这道题的意思是Kim想收集所有n种卡片,每天花费一个金币来抽取卡片。每W天(W=(n-1)!)他才能抽取一张卡片。显然,这需要分步骤来理解。假设他已经有a张卡片,要抽取第a+1张,那么概率就是(n-a)/n。而期望就是1/(n-a)。总的期望就是对所有1/(n-a)求和,最终结果就是n!×(1 + 1/2 + 1/3 + ... + 1/n)。

但是在实现过程中,我遇到了一个问题。因为数字会很大,处理起来容易溢出。我试图用Java来解决这个问题。但是Java的精度处理和运算方式,与C++有些不同。尤其是当乘法涉及到大数时,Java的自动扩展会带来一些意想不到的问题。虽然我最终完成了代码,但在比赛中因为数字过大而超时,未能获得优异成绩。

然后是Problem 2281 Trades,这个问题看起来简单,但实现起来非同容易。问题描述是说,Kim有m元钱,每天可以以一定的价格买入或卖出GTX1920图形卡。他需要根据价格波动来最大化利润。每次交易可以灵活操作,但需要保证资金和库存的合规性。

我针对这道题的思路是,先找出所有的价格单调递增和递减区间。在每个递增区间尽可能买入,在下一个递减区间卖出。为了避免递归的复杂性,我尝试使用贪心算法。在本地区域找到价格的极低点和极高点,然后按顺序操作。

然而,在实际代码实现时,我遇到了几个问题。首先,在极大规模的交易时,数值会变得非常庞大,普通的长整型无法处理。我不得不使用Java的BigInteger来解决这个问题。其次,在每一步的操作过程中,交易次数和金额可能会非常巨大,导致性能问题。但通过多次测试和优化,最终我得到了正确的答案。

总体来说,这两个问题教给我很多东西。特别是大数运算在实际开发中的细节处理需要特别注意。此外,不同编程语言在数学处理上的差异也让我意识到,选择合适的工具和方法尤为重要。如果有机会在更合适的语言和框架中实现相同的算法,可能会有更好的效果。

希望我能在接下来的实践中不断改进。这也是我对编程如此有热爱的原因吧。每一次遇到的难题都让我成长,虽然背头也让人有些苦恼。终于,通过不断的努力,我还是解决了这两个看起来复杂的算法问题!

上一篇:北京师范大学第十六届程序设计竞赛决赛-重现赛&补题
下一篇:省赛练习1——SDKD 2018 Spring Team Contest E&补题

发表评论

最新留言

留言是一种美德,欢迎回访!
[***.207.175.100]2025年05月01日 16时32分48秒