[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;
}

加入对话

2条评论

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注