P8577

Trump__Biden · 2022-10-20 08:17:33 · 题解

题意：

给定一个字符串，是由一个 1 ，两个 2 ，三个 3 ， n 个 n 组成的。需要求出从第 l 位到第 r 位的数字总和。注意，一个两位数占两位。

思路：

先预处理出前整个字符串，用一个数组的第 i 位 f[i] 记录前 i 位的总和，输入 l 和 r 之后，利用 f[r] 和 f[l-1] 的差即是第 r 位去除前 l-1 位后的数字总和也就是答案。

代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,l,r,cnt,tmp,tot,a[1000005],f[1000005];
int main(){
    for(int i=1;i<=1000;i++){
        for(int j=1;j<=i&&cnt<=1e6;j++){
            tmp=i,tot=0;
            while(tmp!=0){
                a[++tot]=tmp%10;
                tmp/=10;
            }
            for(int k=tot;k>=1;k--){
                cnt++;
                f[cnt]=f[cnt-1]+a[k];
            }
        }
    }
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&l,&r);
        printf("%d\n",f[r]-f[l-1]);
    }
    return 0;
}

希望这篇题解可以帮助大家理解这道题。