1 条题解

  • 0
    @ 2023-1-10 9:59:17

    乍一看觉得很像模拟题,也就是从 11 枚举到 mm,接着枚举每个数位上的数字求和。实际上,数据范围太大,模拟是过不了的。这其实是一道数学题。可以考虑统计 [1,m][1,m]mm 个数中各位上是 [1,9][1,9] 的个数。

    例如:12341234,先考虑 nn 个数中个位上分别是 [1,9][1,9] 的个数,先来看 12301230,显然 12301230 里个位是 11 的数有 123123 个,2299 也是 123123 个。

    那么没统计的数字就是 [1230,1234][1230,1234]55 个,显然个位是 11 的又增加 55 个。

    再来看十位:类似的来看 12001200 ,则十位是 [1,9][1,9] 的数各有 120120个,剩下还有 [1201,1234][1201,1234],则十位是 [1,2][1,2] 的个数分别增加 1010 个,十位是 33 的增加 55 个。

    以此类推。

    #include<iostream>
    using namespace std;
    int getm(int n)
    {
        int count=0;
        while(n)
        {
            n/=10;
            count++;
        }
        return count;
    }
    int main()
    {
        int n;
        cin>>n;
        int count[10]={0};
        int p=1,m=getm(n);
        while(m--)
        {
            p*=10;
            int t=(n/p)*p;
            for(int i=1;i<=9;i++)count[i]+=t/10;
            t=n-t;
            int x=t/(p/10);
            for(int i=1;i<x;i++)count[i]+=p/10;
            count[x]+=t-x*(p/10)+1;
        }
        long long ans=0;
        for(int i=1;i<=9;i++)ans+=count[i]*i;
        cout<<ans<<endl;
        return 0;
    }
    
    • 1

    信息

    ID
    10
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者