首页 > 代码库 > BZOJ 1833 ZJOI2010 count 数字计数 数位DP
BZOJ 1833 ZJOI2010 count 数字计数 数位DP
题目大意:求[a,b]间所有的整数中0~9每个数字出现了几次
令f[i]为i位数(算前导零)中每个数出现的次数(一定是相同的,所以只记录一个就行了)
有f[i]=f[i-1]*10+10^(i-1)
然后照例十进制拆分
其中计算[0,999...9]的时候要从1~9枚举最高位,然后其余位调用f[i-1]即可
剩余部分已知位直接乘,未知位调用f[i]
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; ll ans[10],f[20]; inline void Resolve(ll x,ll pos) { while(x) ans[x%10]+=pos,x/=10; } void Digital_DP(ll x,int flag) { int i,j; ll pos,now; for(i=1,pos=10;pos<x;++i,pos*=10) { for(j=0;j<=9;j++) ans[j]+=f[i-1]*9*flag; for(j=1;j<=9;j++) ans[j]+=pos/10*flag; } now=pos/=10;--i; while(now<x) { while(now+pos<=x) { ll temp=now/pos; Resolve(temp,pos*flag); for(j=0;j<=9;j++) ans[j]+=f[i]*flag; now+=pos; } pos/=10;--i; } } int main() { int i; ll a,b,pos; f[1]=1; for(i=2,pos=10;i<=12;i++,pos*=10) f[i]=f[i-1]*10+pos; cin>>a>>b; Digital_DP(b+1,1); Digital_DP(a,-1); for(i=0;i<=9;i++) printf("%lld%c",ans[i],i==9?'\n':' '); }
BZOJ 1833 ZJOI2010 count 数字计数 数位DP
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。