酒泉网站建设推广,python软件,微信信息流广告投放,东莞网站建设 胶粘包装材料#x1f9e0; 算法学习日记 | 今天我用「前缀和」解了两道题#xff0c;原来“预处理”能这么强#xff01; 大家好#xff0c;我是你们的算法学习搭子 #x1f44b; 今天继续我的算法入门之旅#xff0c;重点练习了**前缀和#xff08;Prefix Sum#xff09;**这一高效… 算法学习日记 | 今天我用「前缀和」解了两道题原来“预处理”能这么强大家好我是你们的算法学习搭子 今天继续我的算法入门之旅重点练习了**前缀和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^51 \leq a[i] \leq 1001 \leq l \leq r \leq n1 \leq k \leq 5 $。✅ 我的代码#includebits/stdc.husingnamespacestd;usinglllonglong;constll N1e59;ll a[6][N],prefix[6][N];constll p1e97;intmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn,m;intl,r,k;cinnm;for(inti1;in;i)cina[1][i];for(inti2;i5;i){for(intj1;jn;j){a[i][j](a[i-1][j]*a[1][j])%p;}}for(inti1;i5;i){for(intj1;jn;j){prefix[i][j](prefix[i][j-1]a[i][j])%p;}}for(inti0;im;i){cinlrk;cout((prefix[k][r]-prefix[k][l-1]p)%p)endl;}return0;} 题目二小郑的蓝桥平衡串问题描述平衡串指的是一个字符串其中包含两种不同字符并且这两种字符的数量相等。例如ababab和aababb都是平衡串因为每种字符各有三个而abaab和aaaab都不是平衡串因为它们的字符数量不相等。平衡串在密码学和计算机科学中具有重要应用比如可以用于构造哈希函数或者解决一些数学问题。小郑拿到一个只包含 $ L、、、Q $ 的字符串他的任务就是找到最长平衡串且满足平衡串的要求即保证子串中 $ L、、、Q $ 的数量相等。输入格式输入一行字符串保证字符串中只包含字符 $ L、、、Q $。输出格式输出一个整数为输入字符串中最长平衡串的长度。样例输入LQLL样例输出2评测数据规模对于所有评测数据输入字符串的长度 $ len \leq 1000 $。✅ 我的代码#includebits/stdc.husingnamespacestd;constintN1010;intprefix[N];intmain(){string s;cins;intns.length();prefix[0]0;for(inti0;in;i){if(s[i]L){prefix[i1]prefix[i]1;}else{prefix[i1]prefix[i]-1;}}intans0;for(intl0;ln;l){for(intrl1;rn;r){if(prefix[r]prefix[l]){intlenr-l;if(lenans)anslen;}}}coutans;return0;} 我的思考这两道题虽然看起来完全不同但都用了前缀和的思想区间次方和先预处理出每个幂次的前缀和再用 $ \text{sum}[r] - \text{sum}[l-1] $ 快速回答查询。平衡串用prefix[i]表示从开头到第 $ i $ 位L和Q的差值。当两个位置的prefix值相等时说明中间子串是平衡的。你会发现前缀和的本质是“信息压缩”—— 把一段区间的统计信息压缩成一个数值方便后续快速查询。而且前缀和不仅能处理“和”还能处理“差”、“出现次数”、“奇偶性”等抽象状态。比如在平衡串中我们并不关心具体有多少个L或Q只关心它们的相对数量差。这个差值的变化可以用前缀和来追踪。✅ 总结前缀和的核心是预处理 快速查询适用于多次查询同一数组区间的问题可以扩展到二维、多维、非数值型如字符计数关键在于定义合适的“前缀值”如和、差、次数等时间复杂度预处理 $ O(n) $每次查询 $ O(1) $如果你也在刷算法题不妨试试今天这三道题用最直白的前缀和方法做一遍。有时候简单的预处理也能带来巨大的效率提升。欢迎在评论区贴出你的解法我们一起交流进步