NOIP 2018 普及组 初赛 问题求解 第2题

题面：求1到2018，共有多少个包含数字8的数字

https://mp.weixin.qq.com/s/SdZClhvCv-e0CI1NnqC6uw

昍爸这篇文章中，给出了四个数学非常重要的思想
1.枚举
2.分类计算
3.容斥
4.正难则反

【方法一】：原始的枚举+归纳

0-99有19个含有数字8的数，分别是8，18，28，38，48，58，68，78，80，81，82，83，84，85，86，87，88，89，98；

类似地，100-199，200-299，300-399，400-499，500-599，600-699，700-799，900-999也都有19个包含8的数。

而800-899则有100个包含8的数。

因此，0-999一共有19×9+100=271个数包含有数字8。

同样的道理，1000-1999也有271个数包含有数字8。

最后2008，2018这两个数含有数字8。

总计：271×2+2=544。


【方法二】：分类计算

我们按照包含8的个数来分类。我们先考虑0~1999内的数。

只包含一个8：由于8可以位于个位、十位或百位，千位只能是0（注：0就表示没有千位）或1，因此，一共有3×9×9×2=486个。

恰好包含2个8：由于8可以在个位、十位或百位，一共有C(3, 2)×9×2=54个。

包含3个8：只有2个，即888和1888。

最后，加上2008和2018，一共有486+54+2+2=544个。


【方法三】：容斥原理

记P1, P2, P3分别为1-2018之间个位、十位和百位为8的数的个数， 则有：

P1=  202

P2 = 200

P3 = 200

P1∩P2=20，P1∩P2表示个位和十位同时为8的，xx88, 每100个有1个；

P1∩P3=20,  P1∩P3表示个位和百位同时为8的，x8x8, 每1000个有10个；

P2∩P3=20，P2∩P3表示十位和百位同时为8的，x88x, 每1000个有10个；

P1∩P2∩P3=2, P1∩P2∩P3表示个位、十位、百位同时为8，x888, 共有2个；

根据容斥原理，满足要求的总计：202+200+200-20-20-20+2=544


【方法四】：正难则反

我们先求出0~1999里不含有数字8的数的个数。

根据乘法原理，千位有2种选择，百、十、个位各有9种选择，总计：2×9×9×9=1458

所以，0~1999中包含数字8的数有：2000-1458=542个

（注意：这里我们是按0-1999来算的，一共有2000个数，0也属于不包含数字8的1458个数中的一个。）

最后，再加上2008和2018，一共有544个。