vue组件 ISP list dns react router jquery遍历元素 matlab中log函数 office2016修复 清空input文本框的值 当前时间减一天 svn查看历史版本 centos定时任务 python调用自定义函数 python读取mysql数据 python返回函数 python编程语言 javaswitch javasocket通信 java学习平台 java集合遍历 java自定义异常 java调用接口 linux教程 acmecadconverter 快点蛆虫成就单刷 js倒计时 go程序设计语言 关闭页面 屏幕录像专家注册机 文件压缩工具 php完全自学手册 ps怎么修证件照 软媒u盘启动 c语言小游戏代码 8700和8700k 取小数点后两位函数 ps平面设计基础教程 iar软件 cdr调和工具怎么用 frontpage教程
当前位置: 首页 > 学习教程  > 编程语言

P2602 [ZJOI2010]数字计数

2020/10/8 19:21:29 文章标签:

文章目录ResultResultResultHyperlinkHyperlinkHyperlinkDescriptionDescriptionDescriptionSolutionSolutionSolutionCodeCodeCodeResultResultResult HyperlinkHyperlinkHyperlink https://www.luogu.com.cn/problem/P2602 DescriptionDescriptionDescription 求[L,R][L,R]…

R e s u l t Result Result

...


H y p e r l i n k Hyperlink Hyperlink

https://www.luogu.com.cn/problem/P2602


D e s c r i p t i o n Description Description

[ L , R ] [L,R] [L,R]中各个数字出现的次数

数据范围: L ≤ R ≤ 1 0 12 L\leq R\leq 10^{12} LR1012


S o l u t i o n Solution Solution

数位 d p dp dp
首先枚举我们要求的数字,设 f r e s t , s u m f_{rest,sum} frest,sum表示剩余 r e s t rest rest位,这个数字出现了 s u m sum sum次的个数
考虑前导0和最高位的限制即可


C o d e Code Code

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;LL L,R;
int a[20],m;
LL f[20][20];
inline LL read()
{
	char c;LL d=1,f=0;
	while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;
	while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;
	return d*f;
}
inline LL dfs(int rest,int sum,int x,bool lead,bool limit)//没有前导0时lead为True
{
	if(rest==0) return sum;
	if(lead&&limit==0&&f[rest][sum]!=-1) return f[rest][sum];
	int cancse=limit?a[rest]:9;
	LL res=0;
	for(register int i=0;i<=cancse;i++)
	 res+=dfs(rest-1,sum+((lead||i)&&(i==x)),x,lead||i,limit&&i==cancse);
 	if(lead&&limit==0) f[rest][sum]=res;
	return res;
}
inline LL solve(LL x,int y)
{
	m=0;
	while(x) a[++m]=x%10,x/=10;
	memset(f,-1,sizeof(f));
	return dfs(m,0,y,0,1);
}
signed main()
{
	L=read();R=read();
	for(register int i=0;i<=9;i++) printf("%lld ",solve(R,i)-solve(L-1,i));


本文链接: http://www.dtmao.cc/news_show_250145.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?