[BZOJ 1833] 数字计数

Link:

BZOJ 1833 传送门

Solution:

比较明显的数位DP

先预处理出1~9和包括前导0的0的个数：$pre[i]=pre[i-1]*10+10^{digit-1}$

（可以分为首位和其它位来考虑问题）

求$（L,R）$的个数，可以用$（1，R）-（1，L-1）$差分来做

在求$（1，K）$时，我们先根据预处理的值算出$[0,999....99]$的值（不受边界影响）

接下来从最高位开始尽可能增加$10^n$，直到达到边界后再开始增加$10^{n-1}$

每次对于前面已确定的部分暴力算，而后面不确定的、可任意取值的直接用$pre[i]$统计

Code:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll res[],pre[];  

void split(ll x,ll pos){while(x) res[x%]+=pos,x/=;}

void Digital_DP(ll x,int flag)

{

    int i,j;ll pos=,now;

    for(i=;pos<x;i++)//对[0,99..99]进行统计

    {

        for(j=;j<=;j++)

            res[j]+=pre[i-]**flag;

        for(j=;j<=;j++)

            res[j]+=pos/*flag;

        pos*=;

    }

    now=pos/=;i--;

    while(now<x)

    {

        while(now+pos<=x)

        {

            ll temp=now/pos;

            split(temp,pos*flag);//对已确定部分的暴力统计

            for(j=;j<=;j++)//对可任意取值部分的统一计算

                res[j]+=pre[i]*flag;

            now+=pos;

        }

        pos/=;i--;

    }

}

int main()

{

    int i;ll a,b,pos=;

    pre[]=;

    for(i=;i<=;i++)

        pre[i]=pre[i-]*+pos,pos*=;  

    cin >> a >> b;

    Digital_DP(b+,);Digital_DP(a,-);

    for(i=;i<=;i++) cout << res[i] << " ";

}

Review:

1、对于所有i位中每个数字出现次数的预处理要积累：

$pre[i]=pre[i-1]*10+10^{digit-1}$

2、数位统计中的区间问题，考虑差分，都化为$（1，K）$的形式进行求解

3、数位DP中，特殊处理边界；数字出现次数，特殊处理前导0

巴特西

[BZOJ 1833] 数字计数

Link:

Solution:

Code:

Review:

最新文章

热门文章