UVa 1640 (计数) The Counting Problem

题意:

统计[a, b]或[b, a]中0~9这些数字各出现多少次。

分析:

这道题可以和UVa 11361比较来看。

同样是利用这样一个“模板”,进行区间的分块,加速运算。

因为这里没有前导0,所以分块的时候要多分几种情况。

以2345为例,这是一个四位数,首先要计算一下所有的一位数、两位数以及三位数各个数字出现的个数。

对应的模板分别为n,n*,n**,其中n代表非零数字,*代表任意数字。

考虑这样一个长为l的模板****(l个*),这样的数共10l个,而且各个数字都是等频率出现,所以每个数字出现的次数为l * 10l-1

统计完三位数一下的数字之后,就开始统计四位数字:1***,20**,21**,22**,230*,231*,232*,233*,2340,2341,2342,2343,2344,2345

在统计每个模板时,分这样两块计算:

  • **中该数字出现的次数
  • 前面该数出现的次数,比如22**,前面两个2会重复102
 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int pow10[], cnt[]; int f(int d, int n)
{
char s[];
sprintf(s, "%d", n);
int len = strlen(s);
int ans = ; for(int i = ; i < len; i++)
{
if(i == ) { ans++; continue; }
ans += * cnt[i - ];
if(d > ) ans += pow10[i - ];
} int pre[];
for(int i = ; i < len; i++)
{
pre[i] = (int)(s[i] - '' == d);
if(i) pre[i] += pre[i - ];
} for(int i = ; i < len; i++)
{
int maxd = s[i] - '' - ;
int mind = ;
if(i == && len > ) mind = ;
for(int digit = mind; digit <= maxd; digit++)
{
ans += cnt[len - i - ];
if(i) ans += pre[i - ] * pow10[len - i - ];
if(digit == d) ans += pow10[len - i - ];
}
}
return ans;
} int main()
{
//freopen("in.txt", "r", stdin); pow10[] = ;
for(int i = ; i <= ; i++)
{
pow10[i] = pow10[i - ] * ;
cnt[i] = pow10[i - ] * i;
} int a, b;
while(scanf("%d%d", &a, &b) == && a && b)
{
if(a > b) swap(a, b);
for(int d = ; d <= ; d++)
{
if(d) printf(" ");
printf("%d", f(d, b+) - f(d, a));
}
printf("\n");
} return ;
}

代码君

上一篇:UVA 572 油田连通块-并查集解决


下一篇:Java之美[从菜鸟到高手演变]之JVM内存管理及垃圾回收