洛谷P1836 数页码 题解

题目链接：P1836 数页码

题意：

一本书的页码是从 $1\sim n$ 编号的连续整数：$1,2,3,\cdots,n$。请你求出全部页码中所有单个数字的和，例如第 $123$ 页，它的和就是 $1+2+3=6$。

$1\le n\le 10^9$

容易发现这个东西可以转化为

$1 \sim n$ 中每个数字有多少个

考虑数位dp，详见link

然后把每个数字乘一乘就好了

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()

int x,mi[25],cnt[25],num[25],f[25];
void solve(int x,int *cnt)
{
    int len=0;
    memset(num,0,sizeof(num));
    while(x)
    {
        num[++len]=x%10;
        x/=10;
    }
    for(int i=len; i>=1; i--)
    {
        for(int j=0; j<=9; j++)
            cnt[j]+=f[i-1]*num[i];
        for(int j=0; j<num[i]; j++)
            cnt[j]+=mi[i-1];
        int res=0;
        for(int j=i-1; j>=1; j--)
        {
            res = res * 10 + num[j];
        }
        cnt[num[i]]+=res+1;
        cnt[0]-=mi[i-1];
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    mi[0]=1;
    for(int i=1; i<=18; i++)
    {
        f[i]=f[i-1]*10+mi[i-1];
        mi[i]=10*mi[i-1];
    }
    cin >> x;
    solve(x,cnt);
    int res=0;
    for(int i=0; i<=9; i++)
        res+=cnt[i]*i;
    cout << res << '\n';
    return 0;
}

转载请说明出处