题解 P2602 【[ZJOI2010]数字计数】

2018-01-22 20:37:45


萌新第一次发,想法比较独特猥琐,众dalao见谅。

如果题目给出的数据比较小,我们自然可以悠闲地按位脱离慢慢数。

但是很遗憾啊,数据很不给情面。

作为新时代的好少年,我并不打算想什么高大上的算法(其实是不会写),而是准备走歪门邪道优化。

这里有一个离奇的想法,如果能一次解决成千上万个数字就好了。

接下来,我们经过认真打表仔细分析发现:

N每增长一定值(用1000000比较适合嘿嘿嘿方便),每个数码的出现次数都有规律地增长(600000个)。

为了方便我们的计算,先将两个边界按照笨办法朴素算法处理到a*10^6的形式。

这样一来,我们就可以一次性处理1000000个值(高位的数字解决一下问题不大)。

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

这种解决方案可适用于更大的数据(只要不爆类型)