乘之【牛客tracker 每日一题】

乘之时间限制1秒 空间限制1024M知识点模拟网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述对于给定的由n nn个整数组成的数组{ a 1 , a 2 , … , a n } \{a_1,a_2,…,a_n \}{a1​,a2​,…,an​}小龙和小蛇借助于此数组进行游戏。游戏步骤如下1. 小龙选择一个非空区间[ a , b ] [a,b][a,b]2. 小蛇选择一个非空区间[ c , d ] [c,d][c,d]3. 将选中的区间中的全部元素均乘上k kk得到数组a ′ a′a′游戏只进行一轮三个步骤结束后立即停止。小龙想要让数组a ′ a′a′的元素之和尽可能大小蛇想要让数组a ′ a′a′的元素之和尽可能小。假设双方都采取的是最优策略请你计算操作后得到的数组a ′ a′a′的元素之和。请注意区间[ a , b ] [a,b][a,b]和[ c , d ] [c,d][c,d]可以相交但只结算一次即若某一个位置被小龙和小蛇同时选中依旧只乘一次。输入描述每个测试文件均包含多组测试数据。第一行输入一个整数T ( 1 ≦ T ≦ 100 ) T(1≦T≦100)T(1≦T≦100)代表数据组数每组测试数据描述如下第一行输入两个整数n , k ( 1 ≦ n ≦ 10 5 ; − 100 ≦ k ≦ 100 ) n,k(1≦n≦10^5; −100≦k≦100)n,k(1≦n≦105;−100≦k≦100)代表数组中的元素数量、乘数。第二行输入n nn个整数a 1 , a 2 , … , a n ( − 10 6 ≦ a i ≦ 10 6 ) a_1,a_2,…,a_n(−10^6≦a_i≦10^6)a1​,a2​,…,an​(−106≦ai​≦106)代表数组元素。除此之外保证单个测试文件的n nn之和不超过2 × 10 5 2×10^52×105。输出描述对于每一组测试数据新起一行。输出一个整数代表操作后数组a ′ a′a′的元素之和。示例1输入3 2 4 1 1 6 0 1 1 4 5 1 4 4 -1 -2 1 -10 3输出8 0 8说明对于第一组测试数据小龙的最优策略是选择区间[ 1 , 2 ] [1,2][1,2]一旦这么做了无论小蛇选择的区间是什么都不会影响最终答案。对于第三组测试数据其中一种最优策略为龙选择区间[ 1 , 3 ] [1,3][1,3]小蛇选择区间[ 4 , 4 ] [4,4][4,4]解题思路本题核心是通过博弈最优策略分析简化计算小龙希望数组和最大小蛇希望和最小且双方均采取最优策略。推导可知小龙的最优选择是选中整个数组区间此时无论小蛇选择哪个区间重叠位置仅乘一次k kk最终所有元素都会被乘k kk非重叠位置也因小龙的选择被乘k kk。因此无需枚举区间直接计算原数组所有元素的总和再乘以k kk即可得到操作后的数组和。该方法仅需线性遍历数组求和时间复杂度O ( n ) O(n)O(n)每组适配n ≤ 1 e 5 、总 n ≤ 2 × 10 5 n≤1e5、总n≤2×10^5n≤1e5、总n≤2×105的规模通过博弈策略推导简化计算精准得出最终结果。总结核心逻辑博弈最优策略下小龙选整个数组区间最终所有元素仅乘一次k kk总和为原数组和× k ×k×k。关键操作计算数组元素总和直接乘以k kk得到结果无需枚举区间。效率保障线性遍历计算数组和时间复杂度O ( n ) O(n)O(n)适配题目数据规模要求。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e610;constll mod1e97;constll INF1e18;intmain(){ll T;cinT;while(T--){ll n,k;cinnk;vectorlla(n);for(ll i0;in;i)cina[i];ll resk*accumulate(a.begin(),a.end(),0);coutresendl;}return0;}