2023年信奥赛C++提高组csp-s初赛真题及答案解析（完善程序第2题）

2023年信奥赛C提高组csp-s初赛真题及答案解析完善程序第2题#### 第2题最大值之和给定整数序列a 0 , ⋯ , a n − 1 a_0,⋯,a_{n−1}a0​,⋯,an−1​求该序列所有非空连续子序列的最大值之和。上述参数满足1 ≤ n ≤ 10 5 和 1 ≤ a i ≤ 10 8 1≤n≤10^5和 1≤a_i≤10^81≤n≤105和1≤ai​≤108。一个序列的非空连续子序列可以用两个下标 l和 r其中0≤l≤rn表示对应的序列为a l , a l 1 , ⋯ , a r a_l,a_{l1},⋯,a_ral​,al1​,⋯,ar​。两个非空连续子序列不同当且仅当下标不同。例如当原序列为[ 1 , 2 , 1 , 2 ] [1,2,1,2][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(nlog⁡n)。试补全程序。#includeiostream#includealgorithm#includevectorconstintMAXN100000;intn;inta[MAXN];longlongans;voidsolve(intl,intr){if(l1r){ansa[l];return;}intmid(lr)1;std::vectorintpre(amid,ar);for(inti1;ir-mid;i)①;std::vectorlonglongsum(r-mid1);for(inti0;ir-mid;i)sum[i1]sum[i]pre[i];for(intimid-1,jmid,max0;il;--i){while(jr②)j;maxstd::max(max,a[i]);ans③;ans④;}solve(l,mid);solve(mid,r);}intmain(){std::cinn;for(inti0;in;i)std::cina[i];⑤;std::coutansstd::endl;return0;}①处应填A.pre[i] std::max(pre[i - 1], a[i - 1])B.pre[i 1] std::max(pre[i],pre[i 1])C.pre[i] std::max(pre[i -1], a[i])D.pre[i] std::max(pre[i], pre[i - 1])②处应填A.a[j] maxB.a[j] a[i]C.pre[j - mid] maxD.pre[j - mid] max③处应填A.(long long)(j - mid) * maxB.(long long)(j - mid) * (i - 1) * maxC.sum[j - mid]D.sum[j - mid] * (i - 1)④处应填A.(long long)(r - j) * maxB.(long long)(r - j) * (mid - i) * maxC.sum[r - mid] - sum[j - mid]D.(sum[r - mid] - sum[j - mid]) * (mid - i)⑤处应填A.solve(0n)B.solve(0n - 1)C.solve(1n)D.solve(1n - 1)解题思路该程序使用分治算法计算序列所有非空连续子序列的最大值之和。分治的核心思想是将区间[ l , r ) [l, r)[l,r)分成左右两半[ l , mid ) [l, \text{mid})[l,mid)和[ mid , r ) [\text{mid}, r)[mid,r)递归计算左右内部的贡献再计算跨越中点的子序列的贡献。跨越中点贡献的计算预处理右半部分的前缀最大值数组pre及其前缀和数组sum。对于每个左端点i ii从mid − 1 \text{mid}-1mid−1向左枚举维护左半部分的最大值max \text{max}max并利用双指针j jj将右端点分为两部分右端点j ∈ [ mid , j 0 ) j \in [\text{mid}, j_0)j∈[mid,j0​)区间最大值由左半部分贡献即max \text{max}max。右端点j ∈ [ j 0 , r ) j \in [j_0, r)j∈[j0​,r)区间最大值由右半部分贡献即pre [ j − mid ] \text{pre}[j-\text{mid}]pre[j−mid]。指针j jj的移动条件为a [ j ] a [ i ] a[j] a[i]a[j]a[i]即找到第一个a [ j ] ≥ a [ i ] a[j] \ge a[i]a[j]≥a[i]的位置。答案及解析①D预处理pre为右半部分的前缀最大值。②B移动指针j jj的条件为a [ j ] a [ i ] a[j] a[i]a[j]a[i]。③A第一组贡献为( j − mid ) × max (\text{j} - \text{mid}) \times \text{max}(j−mid)×max。④C第二组贡献为sum [ r − mid ] − sum [ j − mid ] \text{sum}[r-\text{mid}] - \text{sum}[j-\text{mid}]sum[r−mid]−sum[j−mid]。⑤A初始调用为solve(0, n)表示整个区间[ 0 , n ) [0, n)[0,n)。专栏推荐信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html4、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}