分享一类官方解析巨烦无比的枚举题目的简便解法

德鲁菌

Advanced Question的第52题 (ps24851.01)

if whitney wrote the decimal representations for the first 300 positive integer multiples of 5 and did not write any other numbers, how many times would she have written the digit 5?
官方解析用观察数列的方法特别容易数漏，简易用乘法原理做：
1) 假设数字为ABCD (ABCD不同时为0)
2) 当A=1时
    a) 若B=5, 仅“1500”1种组合
    b) 若B≠5，B有0~4五种可能，C有0~9十种可能，D有0或5两种可能
        i) 若C=5, 有5*2=10种组合可能
       ii) 若D=5, 有5*10=50种组合可能
3) 当A=0时，B有0~9十种可能，C有0~9十种可能，D有0或5两种可能
    a) 若B=5, 有10*2种组合可能
    b) 若C=5, 有10*2种组合可能
    c) 若D=5, 有10*10种组合可能
   
∴有1+10+50+20+20+100=201种可能

MavericksX

楼主的思路确实很有帮助，感谢?

linhanrr

fossilw 发表于 2022-7-13 15:11
b) 若B≠5，B有0~4五种可能，C有0~9十种可能，D有0或5两种可能
        i) 若C=5, 有5*2=10种组合可能
     ...

我認為樓主的思路應該是在數各個位數需要'分別'寫幾次5。
若C=5 則會讓數字變成1_5_ 前後兩個空格會造成十位數字5 需要被寫10次
若D=5 數字則是 1_ _ 5 個位數字的5則會需要被寫50次
1355的確實會被兩種方法都考慮到，但差別是在數的位置不同！

fossilw

b) 若B≠5，B有0~4五种可能，C有0~9十种可能，D有0或5两种可能
        i) 若C=5, 有5*2=10种组合可能
       ii) 若D=5, 有5*10=50种组合可能

若C=5, 有5*2=10种组合可能， （这里面包括数字355了吧）
若D=5, 有5*10=50种组合可能 ， （这里也包括数字355了吧）
这种分类是不是有重复？？？？

ellaaaaaa12.18

谢谢分享 楼主思路太好了！！

andrew22要奋斗

感谢分享！               

灭绝人性

Aria1993 发表于 2022-5-25 09:18
没读懂题

我给你举例
b) 若B≠5，B有0~4五种可能，C有0~9十种可能，D有0或5两种可能
        i) 若C=5, 有5*2=10种组合可能
       ii) 若D=5, 有5*10=50种组合可能
ABCD
A 锁死1 B 5可能 C等于 5 D 2可能  因此   i) 若C=5, 有5*2=10种组合可能
以此类推
楼主思路很好 基本上可以搞定所有这类型题目了  和写代码的思路一样

Aria1993

没读懂题

melody想拿offer

很有用，谢谢楼主！

海登卒

有点东西 正好前两天做到这题

打开了新思路

谢谢楼主