动态规划：数位统计DP

数位统计DP"/>

动态规划：数位统计DP

#include<iostream>
#include<vector>
#define ll long longusing namespace std;int get(vector<int>num,int l,int r)//求该位之前的所有位组成的数 
{int res=0;for(int i=l;i>=r;i--)res=res*10+num[i];return res;
}int power10(int x)//求10的该位之后的位数次方
{int res=1;while(x--)res*=10;return res;
}ll count(int n,int x)//返回从1~n所有数中x出现的总数
{if(!n) return 0;//若n是0则直接返回vector<int>num;//把n的每一位抠出来while(n){num.push_back(n%10);n/=10;}n=num.size();//让n为数字的总位数,后面n就是这个数字的位数用来操作long long res=0;//该数出现的次数//这个for统计1~n中x出现的次数,在for循环的时候是让i为最高位开始计算x的次数//如548，则算的顺序:i=2(3-1),算0~9出现的次数，因为是高位没有前位，所以不用进入if算前位//                  i=1，    算0~9出现的次数，因为不是最高位，所以要进入if算前位。//                  i=0,     算0~9出现的次数，因为不是最高位，所以要进入if算前位。//这样就能算出每位上x出现的次数了，用res加每位出现的次数//这里-!x是指，若x==0则不用看最高位，因为一个数字最高位不可能为0for(int i=n-1-!x;i>=0;i--)//例：abcdefg,求d位为x的次数。此时的i为位数，从高到底，最高位为n-1号位，最低位为0号位{//一：d位之前的三位小于abc时(总位数小于数字的位数时+总位数等于数字的位数且前三位小于abc时)：000~abc-1，d位出现的次数为abc*10^efg,即abc*1000if(i<n-1){//求该位之前的所有位组成的数 *10的该位之后的位数次方res+=get(num,n-1,i+1)*power10(i);//每次统计都是从最高位开始统计这个数出现的次数，所以在for里写这个if(!x)是对的，//for是1~n统计，而这里是统计1~n中x每次数字出现的次数,这个if(!x)只会在每次数字发生一次//因为找的是x出现的次数，如果x是0，则x不能是第一位的数字，但上面计算的时候还是算进去了//所以若x为0，则要减去10的后三位数次方，即-1000if(!x) res-=power10(i);}//二：d位之前等于abc时//d位之前的三位等于abc时，分三种：d<x，d=x,d>x//1：d<x，则为0//2:d=x，则后面的三位可以为000~efg，一共efg+1次if(num[i]==x) res+=get(num,i-1,0)+1;//3:d>x，则后面三位可以是000~999,一共1000次else if(num[i]>x) res+=power10(i);}return res;
}int main()
{int a,b;scanf("%d%d",&a,&b);while(a||b)//题目要求ab同时为0时终止{if(a>b)swap(a,b);//保持b>afor(int i=0;i<10;i++)printf("%lld ",count(b,i)-count(a-1,i));//算a~b中的每个数字中i出现的次数printf("\n");scanf("%d%d",&a,&b);}return 0;
}