AcWing 338. 计数问题（用简单（kun nan）的提高课打开）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 338. 计数问题（用简单（kun nan）的提高课打开）原题链接中等

作者：

纪念 , 2020-03-13 21:38:38 , 所有人可见 , 阅读 1250

3

4

题目描述

简洁意思为给定一个区间，求区间中0-9出现的次数。

数据范围
0<a,b<100000000

算法题解

此题由提高课模板改编orz, f(i,j,k)表示一共有i位,且最高位为j的数中,k出现的次数。

f(i,j,k)可由f(i-1,0-9,k)转化而来，如果j=k，那f(i,j,k)就要加上10的i-1次方，例如

求f(2,2,2),由f(1,x,2)转化时候实则开头为2的数的首位2并没有被计算。由此预处理完成

接下来是dp每一位的过程，由于前导零不合法，我们需要特判，而特判比较麻烦，因此判断

如果是首位就从1开始枚举，反之从0开始，最后再暴力枚举1到n-1位数（n为数的总位数）

换句话说，枚举1的时候等价于存在n-1个前导零。另外，dp过程中需要注意的是当此位数

等于我们需要求的数的个数的时候，需要遍历后面位数，遍历原理等同于预处理没有被计算的

部分。细节很多，题主在细节上debug了好久orz 果然还是太菜了。深夜记录写下此文记录一下

辛酸过程。

C++ 代码

#include <iostream>
#include <vector>
using namespace std;
const int N=11;
long long f[N][N][N];
void init()
{
    for(int i=0;i<=9;i++)
    {
        f[1][i][i]=1;
    }
    for(int i=2;i<N;i++)
    {
        long long u=1;
        for(int w=1;w<i;w++)u*=10;
        for(int j=0;j<=9;j++)
        {
            for(int k=0;k<=9;k++)
            {
                for(int z=0;z<=9;z++)
                {
                    f[i][j][k]+=f[i-1][z][k];
                }
                if(j==k)f[i][j][j]+=u;
            }
        }
    }
}
int dp(int n,int r)
{
    if(!n)return 0;
    int t=n;
    vector <int> nums;
    while(n)nums.push_back(n%10),n/=10;
    int res=0,last=-1;
    for(int i=nums.size()-1;i>=0;i--)
    {
        int x=nums[i];
        for(int j=i==nums.size()-1;j<x;j++)
        {
            res+=f[i+1][j][r];
        }
        if(!i)
        {
            while(t)
            {
                if((t%10)==r)res++;
                t/=10;
            }
        }
        if(x==r)
        {
            long long p=0;
            for(int z=i-1;z>=0;z--)
            {
                p=p*10+nums[z];
            }
            res+=p;
        }
    }
    for(int i=1;i<nums.size();i++)
    {
        for(int j=1;j<=9;j++)
        {
           res+=f[i][j][r];
        }
    }
    return res;
}
int main(void)
{
    init();
    int l,r;
    while(cin>>l>>r,l||r)
    {
        if(l>r)swap(l,r);
       for(int i=0;i<=9;i++) 
       {
           cout<<dp(r,i)-dp(l-1,i)<<" ";
       }
       cout<<endl;
    }
    return 0;
}

7 评论

wavecho 2021-03-24 13:55

太强了啊啊啊啊

Retired 2020-08-28 09:07

贴下我改完后的代码
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int N=15;

int f[N][10][10];
//f[i][j][k]一共i位最高位是j，求各个数位是k的数的个数
int a,b;

void init()
{
    for(int i=0;i<=9;i++)
        {
            f[1][i][i]++;
        }
    for(int k=0;k<=9;k++)//k循环也可以放到里边去
        for(int i=2;i<N;i++)
        {
            int u=1;
            for(int w=1;w<i;w++)
                u*=10;
            for(int j=0;j<=9;j++)
            {
                if(j==k)//j要出现在j这层循环里边，不应该循环到x层里边去
                //if和下面的for是同时的，不存在改变先后关系结果不同的情况
                    f[i][j][k]+=u;
                for(int x=0;x<=9;x++)
                {
                    f[i][j][k]+=f[i-1][x][k];
                }
            }
        }

}

int dp(int n,int k)//这道题第一次选数字时不能含前导零
//求0~n中，对于每个数字有多少位是k
{
    if(!n)return r==0?1:0;
    //if(!n)return 0;
    int res=0,last=11;//last记录x，if(last==k)res++; last!=0~9

    vector<int>num;
    while(n)num.push_back(n%10),n/=10;

    for(int i=num.size()-1;i>=0;i--)
    {
        int x=num[i];
        for(int j=i==num.size()-1;j<x;j++)
        {

            res+=f[i+1][j][k];
        }
        last=x;
        if(last==k)res++;

        if(x==k)
        {
            long long p=0;
            for(int z=i-1;z>=0;z--)
            {
                p=p*10+num[z];
            }
            res+=p;
        }

    }

    for(int i=1;i<num.size();i++)
    {
        for(int j=i!=1;j<=9;j++)
        {
           res+=f[i][j][k];
        }
    }
    return res;
}


int main()
{
    init();
    //f[i][j][k]对于f[1][2][i]和1位数是对的
    //for(int i=0;i<=9;i++)
    //cout<<f[2][2][i]<<endl;//不对

    while(cin>>a>>b,a||b)
    {
        if(a>b)swap(a,b);
        for(int i=0;i<=9;i++)
            cout<<dp(b,i)-dp(a-1,i)<<" ";
        cout<<endl;
    }
    return 0;
}

Retired 2020-08-28 09:05

if(!n)return r==0?1:0;
......
......
for(int i=1;i<num.size();i++)
    {
        for(int j=i!=1;j<=9;j++)
        {
           res+=f[i][j][k];
        }
    }

Retired 2020-08-28 08:42

last=x;
if(last==r)res++;

可以替换

while(t)
    {
        if((t%10)==r)res++;
        t/=10;
    }

Retired 2020-08-28 08:40

orz，终于搞懂了，看到这篇题解真的是”wa的一声哭出来 “

纪念 2020-09-15 21:05

谢谢支持~~~~

宇小苏 2020-04-04 13:43

厉害

App 内打开