首页 > [SCOI2010]幸运数字
开通博客写题解
头像 shyyhs
发表于 2021-03-22 18:16:46
思路 本来以为是数位,想不出状态,后来又想着容斥一下以为都是的倍数的数量+的数量-的数量,然后就死了.万万没想到是. 思路很简单,就是先爆搜出那些合法的数/基数,其他数一定是这些数的倍数,然后把爆搜的数去个重,有些数是里面数的倍数,然后从小到大排序一下(剪枝).然后再用容斥原理统计答案即可. 坑点 展开全文
去ta的博客 赞 (3) 回复(2) 收起
头像 jzdx（hjh）
发表于 2021-03-25 23:59:03
题号 NC20278名称 [SCOI2010]幸运数字来源 [SCOI2010] 题目描述 在中国，很多人都把6和8视为是幸运数字！lxhgww也这样认为，于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码，比如68，666，888都是“幸运号码”！ 但是这种“幸运号码”总是 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 sunrise__sunrise
发表于 2021-03-22 18:38:42
Solution 第一眼以为是数位，但是发现如果是倍数也成立的话那就不知道怎么写每位的状态了。 首先我们可以很容易找到从全部的幸运数字，通过一次即可，可以知道最多的初始幸运数字是个，那么我们如何通过这些幸运数字找到答案。 这类倍数题目，考虑容斥处理。首先我们加上中的倍数的个数，这个答案等于，同理我们 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 熠丶
发表于 2021-03-22 21:06:47
做法：dfs+容斥 思路 先找出只含6和8的数，再把那些成倍数关系的给删了 我们知道对于一个幸运号码x，在[l,r]中x的倍数的个数，就是 之后根据容斥（奇加偶减）,答案为选1个幸运号码−选2个幸运号码的lcm+选3个幸运号码的lcm... 注意: 1.在求lcm的时候会爆long l 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Eihuvita.
发表于 2021-03-22 20:15:08
题意 我们称含6和8的号码是“幸运号码”凡是幸运号码的倍数都称为“近似幸运号码” 求一个区间里的“近似幸运号码”个数 直接暴力找到所有的“幸运号码”然后其他的数就一定是这些数的倍数 我们从小到大sort一下 然后找这些数的倍数 然后对这些数进行容斥 统计答案即可 code #include<b 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”