自动搬运

查看原文

来自洛谷，原作者为

	Trump__Biden AFO||抚平回忆留下的疤。||谁念西风独自凉 。

搬运于2025-08-24 22:40:21，当前版本为作者最后更新于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;
}

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