【数学/数位DP】牛客网19寒假R3G
链接:https://ac.nowcoder.com/acm/contest/329/G
来源:牛客网
经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!
处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。
现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。
输入描述:
一行包括两个数字l,r,表示你给处女座展示的数字范围为 [l,r] 。
输出描述:
一行一个整数,表示处女座内心激动的次数。
- 示例1
-
输入
10 20 -
输出
1 -
备注
0≤l≤r≤10^18
此题做法很多。
1. 数学
可以先想求不含6的数有多少个,那么题目实际上是问的去掉6以后,给定一个数,问这个数在不含6的数组成的序列中排第几个。那么可以看成是给定一个9进制数,问在十进制数里排第几个(值是多少)。
比如18,看成九进制1\times9^1 + 7\times9^0 = 16
由于6被去掉了,那么8就排在了第7位。这个思想在很多题目里都可以用到。
那么如果给定的数本来就含6怎么处理呢?
第一,x5999和x6xxx内所包含的 不含6 的数其实是一样多的。
第二,通过列表可以发现,凡是某一位有6的都不存在了,相当于问1和2之间有多少个1。所以对于含6的数,把最高位的6改为5,低位全部改成9就可以了。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,pl,pr;
ll ni[22]={0},num[22]={0};
string
… Read the rest