分享一类官方解析巨烦无比的枚举题目的简便解法 [2020.07.15]
作者:德鲁菌
日期:2020-09-11
Advanced Question 的第 52 题:
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?
官方解析用观察数列的方法特别容易数漏,建议用乘法原理做:
- 假设数字为 ABCD (ABCD 不同时为0)
- 当 A=1 时,
a) 若 B=5, 仅“1500”1 种组合
b) 若 B≠5,B 有 0~4 五种可能,C 有 0~9 十种可能,D 有 0 或 5 两种可能
i) 若 C=5, 有 5x2=10 种组合可能
ii) 若 D=5, 有 5x10=50 种组合可能 - 当 A=0 时,B 有 0~9 十种可能,C 有 0~9 十种可能,D 有 0 或 5 两种可能
a) 若 B=5, 有 10x2 种组合可能
b) 若 C=5, 有 10x2 种组合可能
c) 若 D=5, 有 10x10 种组合可能
所以有 1+10+50+20+20+100=201 种可能。

京公网安备11010202008513号
我認為樓主的思路應該是在數各個位數需要'分別'寫幾次5。
若C=5 則會讓數字變成1_5_ 前後兩個空格會造成十位數字5 需要被寫10次
若D=5 數字則是 1_ _ 5 個位數字的5則會需要被寫50次
1355的確實會被兩種方法都考慮到,但差別是在數的位置不同!
我给你举例
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种组合可能
以此类推
楼主思路很好 基本上可以搞定所有这类型题目了 和写代码的思路一样