处女座和他的小姐姐(三)----数位DP
2024-10-19 21:29:15
链接:https://ac.nowcoder.com/acm/contest/329/G
来源:牛客网
经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666!
处女座其实也挺喜欢6这个数字的,实际上他做手环的时候选取的k=6。所以他对于包含数码6的数字极其敏感。每次看到像4567这样的数字的时候他的心就像触电了一样,想起了小姐姐。
现在你要给处女座展示一系列数字,你想知道他的内心会激动多少次。对于同一个数字,他最多只会激动一次,即如果这个数是66666,他还是只会激动一次。
输入描述:
一行包括两个数字l,r,表示你给处女座展示的数字范围为[l,r]。
输出描述:
一行一个整数,表示处女座内心激动的次数。
备注:
0≤l≤r≤1018
#include<iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef double db;
int shuwei[];
ll dp[][];//dp[i][j],i是当前数位,j是两种情况,j==1表示当前位的这个数为6,j==0表示当前位的这个数不为6
//dp[i][j]表示[0,当前位的数]不含6的个数
ll dfs(int pos,int pre,bool limit)//pos是当前位数,pre是代表两种情况,limit判断是否为上界
{
if(pos==-)//是否超出统计数位
return ;
if(!limit&&dp[pos][pre]!=-)//如果当前数位的数不是6
return dp[pos][pre];
int now=limit?shuwei[pos]:;
ll cnt=;//记录区间内不含6的个数
for(int i=;i<=now;++i)
{
if(i==)
continue;
cnt+=dfs(pos-,i,limit&&(i==now));
}
if(!limit)
dp[pos][pre]=cnt;
return cnt;
}
ll solve(ll x)
{
int d=;
memset(dp,-,sizeof(dp));
while(x)
{
shuwei[d++]=x%;//将数x分解成个十百千位后逆序存进数组
x/=;
}
return dfs(d-,,true);//从最高位开始处理,预留了一个前导零
}
int main()
{
ll n,m;
cin>>n>>m;
ll ans=m-n+-(solve(m)-solve(n-));
cout<<ans<<endl;
return ;
}
最新文章
- Swift3 - String 字符串、Array 数组、Dictionary 字典的使用
- redhat 配置本地yum源163yum源epel 源,无需卸载yum!无须拷贝ISO,愿网上少一点垃圾教程误人子弟
- windows下docker环境设置
- js-DOM,DOM扩展
- IOS开发之网络编程--文件压缩和解压缩
- Redis附加功能之键过期功能
- 关键字 final
- noip 2009 细胞分裂
- Android Studio的Terminal配置
- C实战:项目构建Make,Automake,CMake
- C++编程题#1:含k个3的数
- 洗礼灵魂,修炼python(66)--爬虫篇—BeauitifulSoup进阶之“我让你忘记那个负心汉,有我就够了”
- [No0000124]WPF 扩展控件Behavior的几种方式
- Makefile中变量定义中末尾不能有空格
- BIEE11G配置Oracle 12c数据源
- mysql水平分区
- c#基础学习(0806)之可变参数、ref和out关键字的简单使用
- MVC Linq动态排序
- ios 给键盘上面加上“完成”
- 小程序中 function (res)的理解