链接: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
以后补一下数位dp,先把板子放这
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;
typedef long long ll;
int a[70];
long long int dp[70];
long long int dfs(int pos,bool limit)
{
if(pos==0) return 1;
if(!limit && dp[pos]!=-1) return dp[pos];
int up=limit ? a[pos] : 9;
long long int tmp=0;
for(int i=0;i<=up;i++)
{
if(i==6) continue;//都是保证枚举合法性
tmp+=dfs(pos-1,limit && i==a[pos]);
}
if(!limit) dp[pos]=tmp;
return tmp;
}
long long int solve(long long int x)
{
int pos=0;
long long n=x;
if(x<=0)return 0;
while(x)
{
a[++pos]=x%10;
x/=10;
}
return n+1-dfs(pos,true);
}
int main()
{
long long int le,ri;
//memset(dp,-1,sizeof dp);可优化
while(~scanf("%lld%lld",&le,&ri))
{
memset(dp,-1,sizeof dp);
printf("%lld\n",solve(ri)-solve(le-1));
}
return 0;
}
处女座和小姐姐(三)(数位dp)的更多相关文章
-
牛客寒假算法基础集训营3处女座和小姐姐(三) (数位dp)
链接:https://ac.nowcoder.com/acm/contest/329/G来源:牛客网 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 262144K,其他语言52428 ...
-
牛客训练三:处女座和小姐姐(三)(数位dp)
题目链接:传送门 思路:数位dp的记忆化搜索模板 从高位向低位枚举,逐位确定每一位的6的个数,dp[i][s]表示处理到第i条边,状态为s时的数字的个数. 注意,要使用long long类型. #in ...
-
处女座和小姐姐(三)-数位dp1.0
链接:https://ac.nowcoder.com/acm/contest/329/G来源:牛客网 题目描述 经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666! ...
-
小米oj 找小"3"(数位dp)
找小"3" 序号:#40难度:困难时间限制:1000ms内存限制:10M 描述 给定一个奇数n,可得到一个由从1到n的所有奇数所组成的数列,求这一数列中数字3所出现的总次数.例如 ...
-
uoj#275. 【清华集训2016】组合数问题(数位dp)
传送门 假设有\(k|{n\choose m}\),因为\(n!\)中质因子\(k\)的次数为\(S(n)=\left\lfloor\frac{n}{k}\right\rfloor+\left\lfl ...
-
「动态规划」-数位dp专题
数位dp,今天学长讲的稍玄学,课下花了一会时间仔细看了一下,发现板子是挺好理解的,就在这里写一些: 数位dp主要就是搞一些在区间中,区间内的数满足题目中的条件的数的个数的一类题,题目一般都好理解,这时 ...
-
处女座和他的小姐姐(三)----数位DP
链接:https://ac.nowcoder.com/acm/contest/329/G来源:牛客网 经过了选号和漫长的等待,处女座终于拿到了给小姐姐定制的手环,小姐姐看到以后直呼666! 处女座其实 ...
-
[bzoj3209][花神的数论题] (数位dp+费马小定理)
Description 背景众所周知,花神多年来凭借无边的神力狂虐各大 OJ.OI.CF.TC …… 当然也包括 CH 啦.描述话说花神这天又来讲课了.课后照例有超级难的神题啦…… 我等蒟蒻又遭殃了. ...
-
【好好补题,因为没准题目还会再出第三遍!!】ACM字符串-组合数学(官方题解是数位DP来写)
ACM字符串 .长度不能超过n .字符串中仅包含大写字母 .生成的字符串必须包含字符串“ACM”,ACM字符串要求连在一块! ok,是不是很简单?现在告诉你n的值,你来告诉我这样的字符串有多少个 输入 ...
随机推荐
-
JS中使用MD5加密
下载 MD5 使用MD5加密的方法:下载md5.js文件,在网页中引用该文件: < script type="text/javascript" src="md5.j ...
-
Java基本语法练习
1.编写程序,求100以内的全部素数. 实验源码: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public class F ...
-
ORA-01439: 要更改数据类型, 则要修改的列必须为空
此方法有3处update操作,建议根据实际情况的数据量测试评估效率后选用. 思路:定义要更新数据类型的列为[col_old],数据类型为[datatype_old],临时列为[col_temp],数据 ...
-
详解JavaScript中的this
JavaScript中的this总是让人迷惑,应该是js众所周知的坑之一. 个人也觉得js中的this不是一个好的设计,由于this晚绑定的特性,它可以是全局对象,当前对象,或者…有人甚至因为坑大而不 ...
-
nginx入门篇----功能特性
1.nginx功能特性 可以作为http服务器或者反向代理服务器 能够快速响应静态页面(html)的请求 支持FastCGI.SSL.Virtual Host.URL Rewrite.HTTP.Gzi ...
-
LVS三种模式配置及优点缺点比较
目录: LVS三种模式配置 LVS 三种工作模式的优缺点比较 LVS三种模式配置 LVS三种(LVS-DR,LVS-NAT,LVS-TUN)模式的简要配置 LVS是什么: http://www.lin ...
-
Mac OS X将CSV格式转换为Excel文档格式,Excel转CSV中文乱码问题
一:在Mac上假设你使用Excel打开windows导出的CSV格式文档.你会发现表格中全部的的内容都显示在A列. 那么,怎样恢复正常呢,你能够将CSV格式的文档导入到Excel文档中,这样就正常显示 ...
-
Kubernetes volumes简介
容器中的磁盘文件生命周期比较短暂,在一些比较复杂的容器应用中会产生一些问题.一.容器crash后,kubelet会重启该容器,但这些文件会丢失掉.二.pod中的多个容器经常需要共享文件.因此,Kube ...
-
spark2.1:flatMap的用法
代码示例: val sample_data_combine_result=List( (0,(List(FitModel(4022,1447.92,-8.38983306721434,2.0)),1) ...
-
AUC计算 - 进阶操作
首先AUC值是一个概率值,当你随机挑选一个正样本以及负样本,当前的分类算法根据计算得到的Score值将这个正样本排在负样本前面的概率就是AUC值,AUC值越大,当前分类算法越有可能将正样本排在负样本前 ...