当前位置：首页 > news >正文

算法学习日记 | 前缀和

news 2026/5/12 3:12:35

🧠 算法学习日记 | 今天我用「前缀和」解了两道题，原来“预处理”能这么强！

大家好，我是你们的算法学习搭子 👋
今天继续我的算法入门之旅，重点练习了**前缀和（Prefix Sum）**这一高效的数据预处理技巧。

很多人觉得“前缀和”只是用来快速求区间和的工具，但其实，它是一种通过空间换时间的典型思想。
只要我们提前把信息存好，就能在 $ O(1) $ 时间内回答任意查询。

今天我完整做了两道题，每一道都坚持用最朴素的前缀和逻辑实现。下面我把题目原文和我的原始代码原封不动贴出来，不做任何删减或美化，只为真实记录学习过程。

🔹 题目一：区间次方和

问题描述
给定一个长度为 $ n $ 的整数数组 $ a $ 以及 $ m $ 个查询。
每个查询包含三个整数 $ l, r, k $，表示询问 $ l \sim r $ 之间所有元素的 $ k $ 次方和。
请对每个查询输出一个答案，答案对 $ 10^9 + 7 $ 取模。

输入格式
第一行输入两个整数 $ n, m $，其含义如上所述。
第二行输入 $ n $ 个整数 $ a[1], a[2], \ldots, a[n] $。
接下来 $ m $ 行，每行输入三个整数 $ l, r, k $，表示一个查询。

输出格式
输出 $ m $ 行，每行一个整数，表示查询的答案对 $ 10^9 + 7 $ 取模的结果。

样例输入

5 3 1 2 3 4 5 1 3 2 2 4 3 3 5 1

样例输出

14 99 12

评测数据规模
对于 100% 的评测数据：$ 1 \leq n, m \leq 10^5，，，1 \leq a[i] \leq 100，，，1 \leq l \leq r \leq n，，，1 \leq k \leq 5 $。

✅ 我的代码

#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;constll N=1e5+9;ll a[6][N],prefix[6][N];constll p=1e9+7;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,m;intl,r,k;cin>>n>>m;for(inti=1;i<=n;++i)cin>>a[1][i];for(inti=2;i<=5;++i){for(intj=1;j<=n;++j){a[i][j]=(a[i-1][j]*a[1][j])%p;}}for(inti=1;i<=5;++i){for(intj=1;j<=n;++j){prefix[i][j]=(prefix[i][j-1]+a[i][j])%p;}}for(inti=0;i<m;++i){cin>>l>>r>>k;cout<<((prefix[k][r]-prefix[k][l-1]+p)%p)<<endl;}return0;}

🔹 题目二：小郑的蓝桥平衡串

问题描述
平衡串指的是一个字符串，其中包含两种不同字符，并且这两种字符的数量相等。

例如，ababab和aababb都是平衡串，因为每种字符各有三个，而abaab和aaaab都不是平衡串，因为它们的字符数量不相等。

平衡串在密码学和计算机科学中具有重要应用，比如可以用于构造哈希函数或者解决一些数学问题。

小郑拿到一个只包含 $ L、、、Q $ 的字符串，他的任务就是找到最长平衡串，且满足平衡串的要求，即保证子串中 $ L、、、Q $ 的数量相等。

输入格式
输入一行字符串，保证字符串中只包含字符 $ L、、、Q $。

输出格式
输出一个整数，为输入字符串中最长平衡串的长度。

样例输入

LQLL

样例输出

评测数据规模
对于所有评测数据，输入字符串的长度 $ len \leq 1000 $。

✅ 我的代码

#include<bits/stdc++.h>usingnamespacestd;constintN=1010;intprefix[N];intmain(){string s;cin>>s;intn=s.length();prefix[0]=0;for(inti=0;i<n;++i){if(s[i]=='L'){prefix[i+1]=prefix[i]+1;}else{prefix[i+1]=prefix[i]-1;}}intans=0;for(intl=0;l<=n;++l){for(intr=l+1;r<=n;++r){if(prefix[r]==prefix[l]){intlen=r-l;if(len>ans)ans=len;}}}cout<<ans;return0;}