Digital Count数位统计

B -- Digital Count

Time Limit：1s Memory Limit：1024MByte

Submissions：522Solved：117

DESCRIPTION

Given three integers a, b, P, count the total number of digit P appearing in all integers from a to b.

INPUT The first line is a single integer $T$, indicating the number of test cases. For each test case: There are only three numbers $a,b,P$ (0≤a≤b≤2 31-1, 0<P<10). OUTPUT For each test cases: Print the total appearances of digit $P$ from $a$ to $b$ in a single line. SAMPLE INPUT 2 1 10000 1 1 10 1 SAMPLE OUTPUT 4001 2

思路，预处理1位，2位，3位，...，n位的情况

定义f(i,j)为i开头后面跟着j位的范围为 i*10^j~(i+1)^j-1内p出现的次数

举例来说f(2,1))表示20～29范围内出现p的次数

所以有下列递推式：

当 j ≠ p --> f[ i , j ] = Σ f[ k, j-1 ]k=0..9      当 j = p --> f[ i , j ] = Σ f[ k, j-1 ]k=0..9 + 10j

AC源码：

#include <iostream> #include <cstring> #include <stack> #include <queue> #include <cmath> #include <algorithm> typedef long long LL; using namespace std; const int MAXN=10; LL f[MAXN][MAXN]; void init(int p) { for(int i=0;i<=9;++i) f[i][0]=0; for(int j=0;j<=9;++j) if(j==p) f[j][0]=1; for(int j=1;j<=9;++j) { for(int i=0;i<=9;++i) { for(int k=0;k<=9;++k) { f[i][j]+=f[k][j-1]; } if(i==p) f[i][j]+=pow(10,j); } } } LL count(int n,int p) { queue<int> que; stack<int> stk; int num=n; while(num>0) { stk.push(num); num/=10; } while(!stk.empty()) { que.push(stk.top()); stk.pop(); } num=n; LL cnt=0; while(!que.empty()) { int len=que.size(); if(len==1) { for(int i=0;i<=que.front();i++) cnt+=f[i][len-1]; break; } for(int i=0;i<=que.front()-1;i++) cnt+=f[i][len-1]; if(que.front()==p) cnt+=num-que.front()*pow(10,len-1)+1; num=num-que.front()*pow(10,len-1); que.pop(); } return cnt; } void show() { for(int j=0;j<=9;++j) { for(int i=0;i<=9;++i) { cout<<f[i][j]<<" "; } cout<<endl; } } int main() { int T; cin>>T; while(T--) { memset(f,0,sizeof(f)); int a,b,p; cin>>a>>b>>p; init(p); //调试 // show(); cout<<count(b,p)-count(a-1,p)<<endl; } return 0; }