[ZJOI2010 count 数字计数]统计

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1833
【算法分析】
就是从高到低枚举每一位，然后试填比它原位小的数，然后后面的位就可以随便填。这个随便填的话，显然000…000到999…999这一连串中，0-9的数量肯定是一样的。
所以每一位分别+上 (999..999+1)*log (999.999+1)/10。
利用这个快速算，很容易就得解。
【其它】比较繁琐= =，WA了几次。。。
【CODE】
#include #include #include #include using namespace std;
typedef long long lld;
lld L[10];
lld a[10],b[10];
void f(lld x,lld *res){
int i,j,Log=0;
memset(L,0,sizeof(L));
lld mul=1;
while (mul<=x){
mul*=10;
Log++;
}
mul/=10; Log–;
while (mul){
for (i=1;i res[i]+=mul;
for (j=0;j<10;j++){
res[j]+=L[j]*mul;
res[j]+=mul*Log/10;
}
}
L[x/mul%10]++;
mul/=10;
Log–;
if (mul){
for (i=1;i<10;i++){
res[i]+=mul;
for (j=0;j<10;j++)
res[j]+=mul*Log/10;
}
if (x/mul%10){
for (i=0;i<10;i++){
res[i]+=mul*Log/10;
res[i]+=L[i]*mul;
}
res[0]+=mul;
}
}
}
}

int main(){
lld x,y;
cin >> x >> y;
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
f(x,a);
f(y+1,b);
for (int i=0;i<10;i++)
cout << b[i]-a[i] << " ";
cout << endl;
}