[CoE R5] 暴龙的白菜
题目背景
暴龙爱吃白菜。
题目描述
给定一个字符串，由 \(1\) 个 \(\texttt{1}\)，\(2\) 个 \(\texttt{2}\)，\(3\) 个 \(\texttt{3}\)，\(4\) 个 \(\texttt{4}\)，\(5\) 个 \(\texttt{5}\)，\(6\) 个 \(\texttt{6}\)，\(7\) 个 \(\texttt{7}\)，\(8\) 个 \(\texttt{8}\)，\(9\) 个 \(\texttt{9}\)，\(10\) 个 \(\texttt{10}\)……以此类推，依次拼接而成。
询问字符串第 \(l\) 位到第 \(r\) 位的数字之和。
输入格式
输入包含多组测试数据。
第一行一个正整数 \(T\)。
接下来 \(T\) 组问询，每次两个正整数 \(l,r\)。
输出格式
\(T\) 行，每行一个整数代表答案。
样例 #1
样例输入 #1
4
5 9
46 50
114 514
19 19810
样例输出 #1
18
3
1134
74924
提示
样例解释
字符串为：
\[\texttt{12233344445555566666677777778888888899999999910101010101010101010}\cdots\cdots \]对于第一组询问，第 \(5\) 位到第 \(9\) 位的数字之和为 \(3+3+4+4+4=18\)。
对于第二组询问，第 \(46\) 位到第 \(50\) 位的数字之和为 \(1 + 0 + 1 + 0 + 1 = 3\)。
数据范围
本题采用捆绑测试。
- \(\texttt{Subtask 1(10 pts)：}T=1\)，\(1\le l\le r\le 10\)；
- \(\texttt{Subtask 2(20 pts)：}1\le T\le 10\)，\(1\le l\le r\le 10^3\)；
- \(\texttt{Subtask 3(30 pts)：}1\le T\le 10^3\)，\(1\le l\le r\le 10^5\)；
- \(\texttt{Subtask 4(40 pts)：}\)无特殊限制。
对于 \(100\%\) 的数据，满足 \(1\le T\le 10^5\)，\(1\le l\le r\le 10^6\)。
思路
直接暴力获得拼得字符串，再用前缀和\(O(1)\)查询。
代码
#include <iostream>
using namespace std;
const int N = 1000010;
string s = "";
int sum[N];
int get (int x) {
int t = 0;
while (x > 0) t++,x /= 10;
return t;
}
int main () {
int cnt = 0;
for (int i = 1;cnt <= 1000000;i++) {
for (int j = 1;j <= i && cnt <= 1000000;j++) s += to_string (i),cnt += get (i); //暴力
}
for (int i = 1;i <= 1000000;i++) sum[i] = sum[i - 1] + s[i - 1] - '0';
int T;
cin >> T;
while (T--) {
int l,r;
cin >> l >> r;
cout << sum[r] - sum[l - 1] << endl; //前缀和
}
return 0;
}