P2602 [ZJOI2010] 数字计数 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
数位DP模板题
由于是对0~9进行统计,所以我们只需对每一个数进行数位DP即可
不过对于0和1~9还是有区别的
对于dfs维度:pos,lim,zero,dig,sum (dig表示枚举的数字,sum表示在这当前这个大数字中dig出现的次数)
solution:
统计0:如果都是前导0,那么就算现在枚举0,sum也不能加进去
如果前面不是前导0,就正常加
统计1~9,正常加数
好像也没啥可将的
Code:
#include<bits/stdc++.h> using namespace std; #define ll long long #define mp make_pair #define pb push_back //vector函数 #define popb pop_back //vector函数 #define fi first #define se second const int N=20; //const int M=; //const int inf=0x3f3f3f3f; //一般为int赋最大值,不用于memset中 //const ll INF=0x3ffffffffffff; //一般为ll赋最大值,不用于memset中 int len,a[N]; ll l,r,dp[N][N][2][2]; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} return x*f; } ll dfs(int pos,bool lim,bool zero,int dig,ll sum) { if(pos==len+1) return sum; if(dp[pos][sum][lim][zero]!=-1) return dp[pos][sum][lim][zero]; ll res=0; int num=lim?a[pos]:9; for(int i=0;i<=num;i++) { if(dig==0) { if(zero) res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum); else res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum+(i==dig) ); } else res+=dfs(pos+1,lim && i==num,zero && i==0 ,dig,sum+ (i==dig) ); // sum + i==dig 是错的,sum+(i==dig)是对的 } return dp[pos][sum][lim][zero]=res; } ll solve(ll x,int dig) { len=0; memset(dp,-1,sizeof(dp)); for(;x;x/=10) a[++len]=x%10; reverse(a+1,a+len+1); return dfs(1,1,1,dig,0); } int main() { // freopen("","r",stdin); // freopen("","w",stdout); scanf("%lld%lld",&l,&r); for(int i=0;i<=9;i++) printf("%lld ",solve(r,i)-solve(l-1,i)); return 0; }
标签:ch,const,计数,int,ll,dig,ZJOI2010,P2602,define From: https://www.cnblogs.com/Willette/p/17066313.html