关于火柴棒组成最大数的一点理解QWQ
查看原帖
关于火柴棒组成最大数的一点理解QWQ
409914
kasuganoharuka楼主2021/8/12 18:37

做这道题的时候参考大佬们的题解有很多引用了1111,1000,999,711等数据,看到不少小伙伴对此不是很清楚,在这里简单说一下我的理解。(蒟蒻第一次发帖,欢迎大佬们指正)


看到题目保证火柴数不超过24,很容易使人想到暴力出奇迹枚举的方式。那么就来到了问题的关键,如何确定枚举的范围(c的最大值)?

可以明确的是+与=必定占用4根火柴,那么最多只能有20根火柴可供使用。等式的形式为a+b=c,c由a,b两数相加得来,则c的位数一定等于a,b中最大位数或者比其多一位。仔细想想就会发现c所用的火柴数一定小于a,b所用火柴数之和,这里不多赘述,即任何时候c所用的火柴数必定小于10根。

然后就可以去推断c的最大值,依据也是上面的推论。


(附0~9对应需要火柴数:6,2,5,5,4,5,6,3,7,6)

推算c的最大值,这里还是从位数入手,从大位数向小位数降位推导。假定c为五位数(五位数比较容易开始论证,再多反正不可能……),那c所用火柴最少的拼法就是11111,需要10根,不成立,所以c最大值不是五位数。

接着假定c的最大值是四位数。此时给c赋初始最大值7711(推导过程中只使用7,1,1所用最少,7性价比最高,其他数字一旦引用就会GG,以下不再逐一分析其实就是我懒)。7711用了10根火柴,不成立,改为7111,还剩11根可用,那么我们用这11根试着拼a,b中的较大数,第一位只能拼7,后三位每位数字都不大于1,拼1有剩余,拼0就不够,所以7111也不成立。

那么就假定c的最大值是1111罢。此时还剩12根,而1111可能由两个三位数组成,这一下讨论起来复杂度骤增,但是,

我不讨论了,JOJO!


1111的数据已经足够接近真实值,完全可以以此进行枚举,时间复杂度上也不存在问题。

笔者写完代码后在每一个符合条件的式子后面加入了输出,得到最极端的式子应该是711+0=711。

再进行尝试后发现,711~2000的数据都可以AC。

也就是说,只要推断出a,b中的最大位数为三位数,即可进行枚举。


以上是本蒟蒻的理解,可能不够严谨科学,欢迎纠正。

感谢阅读。

第一遍写这个帖子的时候手贱切点了别的页面,回来全没了555

2021/8/12 18:37
加载中...