https://www.luogu.org/PRoblem/show?pid=2602 數位dp是dp的一種，一般來說這種東西至少要一個預處理數組 這種題目你只要靠自己的力量成功搞掉一道，基本上思路都是在的，和背包很像，是有模板的； 我們先弄一個f[i]表示位數位i時，所有情況中0這個數字出現的次數 注意這里的i位是可以有前導0的； 我們前導0和無前導0的情況都要算，那么用前導0的f[]去算無前導0的數時會比反著來更方便，當然，你可以開兩個數組； 比如i=1 那么可能為 0~9 ，所以f[1]=1; i=2時是 00~99所以… 其實很顯然當無前導0時，各個數字出現的次數是一樣的； 所以f[i]表示就講好了； 很顯然f[i]=f[i-1]+10^(i-1); 然后對于一個數，比如5634 我們先算0~999 再算1000~4999 然后單獨吧最高位5出現的次數搞好 就變成了634； 先算100~500；在搞最高位6 然后只有34了； 34同里； 簡單來說，就是先吧0~9999..的算好 再把最高位算好； 注意最高位不可以是0，這種情況要排除 然后就一位一位推下去，比較煩
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cstdlib>#include<cmath>#define Ll long longusing namespace std;Ll f[50],a[50],ans[50],v[50];Ll n,m;void cfb(Ll x){ memset(v,0,sizeof v); if(x==-1)return; if(!x){v[0]=1;return;} Ll n=0; while(x){a[++n]=x%10;x/=10;}//算位數 for(int i=0;i<=9;i++)v[i]=f[n-1];//0~999…… for(int i=1;i<=n-2;i++)v[0]-=pow(10,i); for(int i=1;i<=a[n]-1;i++)v[i]+=pow(10,n-1);//先把最高位搞好，因為最高位不可以0，所以先搞 for(int i=0;i<=9;i++)v[i]+=f[n-1]*(a[n]-1); Ll k=0; for(int i=n-1;i>=1;i--)k=k*10+a[i]; v[a[n]]+=k+1; n--; while(n){//一位一位下去 for(int i=0;i<=a[n]-1;i++)v[i]+=pow(10,n-1); for(int i=0;i<=9;i++)v[i]+=f[n-1]*a[n]; k=0; for(int i=n-1;i>=1;i--)k=k*10+a[i]; v[a[n]]+=k+1; n--; }}int main(){ for(int i=1;i<=12;i++)f[i]=f[i-1]*10+pow(10,i-1); scanf("%lld%lld",&n,&m); cfb(m); for(int i=0;i<=9;i++)ans[i]=v[i]; cfb(n-1); for(int i=0;i<=9;i++)cout<<ans[i]-v[i]<<' ';}新聞熱點
疑難解答
