首页 > 代码库 > 数字0-9的数量
数字0-9的数量
数字0-9的数量
基准时间限制:1 秒 空间限制:131072 KB
给出一段区间a-b,统计这个区间内0-9出现的次数。
比如 10-19,1出现11次(10,11,12,13,14,15,16,17,18,19,其中11包括2个1),其余数字各出现1次。
Input
两个数a,b(1 <= a <= b <= 10^18)
Output
输出共10行,分别是0-9出现的次数
Input示例
10 19
Output示例
11111111111
分析:数位dp做多了发现这题还是挺简单;
dp[pos][x][y]三维分别代表位置,当前要统计的数,当前出现了几个;
注意前导0不算即可;
代码:
#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <bitset>#include <map>#include <queue>#include <stack>#include <vector>#define rep(i,m,n) for(i=m;i<=n;i++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define sys system("pause")const int maxn=1e5+10;const int N=5e4+10;const int M=N*10*10;using namespace std;inline ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}inline ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline void umax(ll &p,ll q){if(p<q)p=q;}inline void umin(ll &p,ll q){if(p>q)p=q;}inline ll read(){ ll x=0;int f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int n,m,k,t,num[20],pos;ll dp[20][10][20],p,q,ans[10];ll dfs(int pos,int x,int y,int z,int k){ if(pos<0)return y; if(z&&k&&dp[pos][x][y]!=-1)return dp[pos][x][y]; int now=z?9:num[pos],i; ll ret=0; rep(i,0,now)ret+=dfs(pos-1,x,!i&&!k?y:(i==x?y+1:y),z||i<num[pos],k||i); return z&&k?dp[pos][x][y]=ret:ret;}void gao(ll x,ll y){ pos=0; while(y)num[pos++]=y%10,y/=10; int i; rep(i,0,9)ans[i]=0,ans[i]+=dfs(pos-1,i,0,0,0); pos=0; while(x)num[pos++]=x%10,x/=10; rep(i,0,9)ans[i]-=dfs(pos-1,i,0,0,0);}int main(){ int i,j; memset(dp,-1,sizeof(dp)); scanf("%lld%lld",&p,&q); gao(p-1,q); rep(i,0,9)printf("%lld\n",ans[i]); return 0;}
数字0-9的数量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。