本文主要是介绍CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
一、题目阅读
(最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。
一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar。两个非空连续子序列不同,当且仅当下标不同。
例如,当原序列为 [1,2,1,2] 时,要计算子序列 [1]、[2]、[1]、[2]、[1,2]、[2,1]、[1,2]、[1,2,1]、[2,1,2]、[1,2,1,2] 的最大值之和,答案为 18。注意 [1,1] 和 [2,2] 虽然是原序列的子序列,但不是连续子序列,所以不应该被计算。另外,注意其中有一些值相同的子序列,但由于他们在原序列中的下标不同,属于不同的非空连续子序列,所以会被分别计算。
解决该问题有许多算法,以下程序使用分治算法,时间复杂度 O(nlogn)。
试补全程序。
#include <iostream> #include <algorithm> #include <vector>const int MAXN = 100000;int n; int a[MAXN]; long long ans;void solve(int l, int r) {if (l + 1 == r) {ans += a[l];return;}int mid = (l + r) >> 1;std::vector<int> pre(a + mid, a + r);for (int i = 1; i < r - mid; ++i) ①;std::vector<long long> sum(r - mid + 1);for (int i = 0; i < r - mid; ++i)sum[i + 1] = sum[i] + pre[i];for (int i = mid - 1, j = mid, max = 0; i >= l; --i) {while (j < r && ②) ++j;max = std::max(max, a[i]);ans += ③;ans += ④;}solve(l, mid);solve(mid, r); }int main() {std::cin >> n;for (int i = 0; i < n; ++i)std::cin >> a[i];⑤;std::cout << ans << std::endl;return 0; }
二、程序分析
主要思路:将数组分成两部分,分别求解两部分的最大矩形和,然后合并两部分的结果。在合并的过程中,考虑跨越中点的最大矩形,通过预处理和前缀和技巧优化计算。
这篇关于CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!