今天正在刷洛谷P8577 [CoE R5] 暴龙的白菜这道题，题目链接：https://www.luogu.com.cn/problem/P8577，有许多心得，供大家参考。
一、模拟
我看了看题目的算法标签，“模拟"？我但是就认为是一个大水题，一看数据范围，更加确定了自己的想法，于是开始模拟！
首先我将1~r的所有序列预处理号，最后l~r累加。
代码如下：
1 #include <iostream>
2 using namespace std;
3
4 int main() {
5 int T;
6 cin >> T;
7 while (T--) {
8 string s;
9
10 int l, r;
11 cin >> l >> r;
12 for (int i = 1; i <= r; i++) {
13 for (int j = 1; j <= i; j++) {
14 s += to_string(i);
15 }
16 }
17 int ans = 0;
18 for (int i = l; i <= r; i++)
19 ans += s[i - 1] - '0';
20 cout << ans << endl;
21
22 }
23
24 return 0;
25 }
30分？#4~#10全部TLE，不在我的预估内啊，我又一算，欸，好像真会超时哦。
于是我又开始苦思冥想其它方法……
二、找规律
我列出了以下玩意儿：
不难发现，红色为开始的数，他们递增的差是递增的。
所以我们就可以枚举开始的数，再用l-第一个穿插的数，用r-l+1去减(l-第一个穿插的数），有些难理解，举个例子：
如：
l=5 r=9 l-3=5-3=2 2*=3 ==6 9-5+1=5 5-2=3 3*=4 ==12 12+6==18 则L~r的和为18
这下懂了吧……
但，60？？？？？？？？
我晕了。
看来规律能拯救这个天下是假的。
三、前缀和
我看了大佬们的提示，用前缀和做。
但，
我没学啊！！！！
但，
聪明的yexc怎么可能放弃呢？
我，看了https://blog.csdn.net/weixin_52477733/article/details/121739364。
这下懂了……
满分Code:
#include <iostream>
#include <algorithm>
using namespace std;
template<typename T=int>
inline T read(){
T X=0; bool flag=1; char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-') flag=0; ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<1)+(X<<3)+(ch^48),ch=getchar();
if(flag) return X;
return ~(X-1);
}
template<typename T=int>
inline void write(T X){
if(X<0) putchar('-'),X=~(X-1);
T s[20],top=0;
while(X) s[++top]=X%10,X/=10;
if(!top) s[++top]=0;
while(top) putchar(s[top--]+'0');
putchar('\n');
}
const int N=1e6+5;
int t,l,r;
int x;
string s,ss;
int a[N];
void init(){
s+="0",x=1;
while(s.size()<N){
int tt=x;
while(tt) ss+=tt%10+'0',tt/=10;
reverse(ss.begin(),ss.end());
for(int i=1; i<=x && s.size()<N; i++)
s+=ss;
ss.clear();
x++;
}
for(int i=1; i<N; i++)
a[i]+=a[i-1]+s[i]-'0';
}
int main(){
init();
t=read();
while(t--){
l=read(),r=read();
write(a[r]-a[l-1]);
}
return 0;
}
哎~
四、后记
今天的题目让我很又有收获，既有模拟的失败，找到规律的兴奋，与学习前缀和的抓耳挠腮，相信只有这种学习态度才能学好。
晚了，2022-12-7 22:01:07，我写完了这篇分享，下次的目标是弄懂一道超级难的题，是什么能让这个蒟蒻如此不堪？
未完待续……
标签：R5,P8577,ch,暴龙,int,12,include From： https://www.cnblogs.com/LuoGuyexc/p/16964706.html