题解 P2602 【[ZJOI2010]数字计数】
吹雪吹雪吹
2018-01-22 20:37:45
萌新第一次发，想法比较~~独特~~猥琐，众dalao见谅。
如果题目给出的数据比较小，我们自然可以悠闲地按位脱离慢慢数。
但是很遗憾啊，数据很不给情面。
作为新时代的~~懒~~好少年，我并不打算想什么高大上的算法（~~其实是不会写~~），而是准备~~走歪门邪道~~优化。
这里有一个离奇的想法，如果能一次解决成千上万个数字就好了。
接下来，我们经过~~认真打表~~仔细分析发现：
N每增长一定值（用1000000比较~~适合嘿嘿嘿~~方便），每个数码的出现次数都有规律地增长（600000个）。
为了方便我们的计算，先将两个边界按照~~笨办法~~朴素算法处理到a\*10^6的形式。
这样一来，我们就可以一次性处理1000000个值（高位的数字解决一下问题不大）。
```cpp
#include<cstdio>
#define n50 600000 //随着n61变化而变化
#define n61 1000000 //便于处理
using namespace std;
long long a[10],n,m;
const long long num[7]={1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000};//10的x次幂
inline long long read()
{
char ch=getchar();long long ret=0,f=1;
while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
bool work(long long x)
{
while(x)
{
a[x%10]++;
x/=10;
}
} //土办法按位脱离
int main()
{
// freopen("count.in","r",stdin);
// freopen("count.out","w",stdout);//文件什么的不重要
n=read(),m=read();
while(n%1000000!=0&&n<m)
{
work(n);n++;
//把n处理成a*10^6
}
while(m%1000000!=0&&m>n)
{
work(m);m--;
//把m处理成a*10^6
}
while(n!=m)
{
for(int i=0;i<10;++i)
a[i]+=n50;
//直接滚过10^6
int i=0;
while(n/num[i])
{
a[(n/num[i])%10]+=n61;//注意！高位数字出现了10^6次！而不是传统的600000次！
i++;
//处理高位
}
n+=n61;
//向前滚动
}
work(m);//处理一下边界
for(int i=0;i<=9;++i)
printf("%lld ",a[i]);
return 0;
}
```
这种解决方案可适用于更大的数据（只要不爆类型）