首页 > 其他分享 >牛客2.7比赛E,F题

牛客2.7比赛E,F题

时间:2024-02-12 11:11:34浏览次数:30  
标签:比赛 leq 1000000000 子段 交换 牛客 数组 100 2.7

链接:https://ac.nowcoder.com/acm/contest/67743/E
来源:牛客网

智乃最近学习了冒泡排序和最长子段和,所以她现在想把它们合并成一个新的算法。

众所周知,冒泡排序是一种通过交换相邻元素实现排序的算法,最长子段和是指从一个数组aaa中取出一段连续的非空数组区间[l,r][l,r][l,r],最大化数组区间的和∑i=lrai\sum_{i=l}^{r}a_{i}∑i=lr​ai​。

现在智乃有一个长度大小为NNN的数组,数组中元素的值有正有负。她想要先进行恰好KKK次相邻元素的交换操作,再求整个数组的最大子段和。她想要让最后求出的最大子段和尽可能的大,请你帮助智乃算出她最终可能的最大子段和有多大。

输入描述:

第一行输入两个正整数N,K(2≤N≤103,0≤K≤100)N,K(2\leq N \leq 10^3,0 \leq K \leq 100)N,K(2≤N≤103,0≤K≤100)表示数组的长度,交换的次数。

接下来一行NNN个整数,输入数组元素ai(−109≤ai≤109)a_i(-10^{9} \leq a_{i} \leq 10^{9})ai(−109≤ai≤109)表示数组元素的值。

输出描述:

仅一行一个整数,表示交换后能取到的非空最大子段和是多少。

​ 示例1

输入

[复制](javascript:void(0)

标签:比赛,leq,1000000000,子段,交换,牛客,数组,100,2.7
From: https://www.cnblogs.com/HLZZPawa/p/18013738

相关文章

  • 2024牛客寒假算法基础集训营2 补题
    2024牛客寒假算法基础集训营2补题A.TokitsukazeandBracelet签到模拟参考代码:#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#defineebemplace_back#defineall(u)u.begin(),u.end()#defineendl'\n'#definedebug(x)cout......
  • 2024牛客寒假算法基础集训营1
    D.数组成鸡题解观察到\(abs(M)\leq1e9\),容易知道如果绝对值不为\(1\)的数的个数大于\(30\)个的话,显然溢出,不会在答案的范围内再仔细分析性质,如果整个数组中数的种类超过了\(20\)种,那么除了\(0\)之外,最坏的结果就是\(-10,-9...-1,1,2,...10\)这样的情况,他们......
  • 2024牛客寒假算法基础集训营1 补题
    2024牛客寒假算法基础集训营1补题A.DFS搜索模拟题意:给你一个字符串\(S\),求出\(S\)中是否存在子序列“DFS“和"dfs"。思路:直接模拟即可参考代码:#include<bits/stdc++.h>usingnamespacestd;#definefffirst#definesssecond#defineebemplace_back#define......
  • 2024牛客寒假算法基础集训营3
    2024牛客寒假算法基础集训营3A.智乃与瞩目狸猫、幸运水母、月宫龙虾思路:就是一个简单的字符串#include<bits/stdc++.h>usingnamespacestd;voidsolve(){stringa,b;cin>>a>>b;if(a[0]==b[0]||a[0]-'A'+'a'==b[0]||b[0]-'A'+'a'==......
  • 牛客寒假集训营 第三场
    这场做了6题,没有做全场,做了个半场吧,还算可以,最后一题磨了很久。A.智乃与瞩目狸猫、幸运水母、月宫龙虾思路分析:是个语法题,单独拿首字母出来全部化成大写然后再判断就可以了。code:点击查看代码#include<bits/stdc++.h>usingnamespacestd;#defi......
  • 2.7
    今天写了一个实例,下图是完整的效果。 <!--pages/home/home.wxml--><swiperindicator-dotscircular><swiper-itemwx:for="{{swiperList}}"wx:key="id"><imagesrc="{{item.image}}"></image></swi......
  • 寒假day6 2.7_2
    讲师:施开成,CTSCrk6!!!数学01分数规划USACO18OPEN二分答案,转化答案,发现\(\sum(w_i-ct_i)\ge0\)随后背包解决问题。数论模\(p\)意义:忽略一个数的具体值,只关心在对\(p\)做除法后的余数。对于模合数,一定要避免除法。逆元将\(\frac{a}{b}\)视为\(a\times(\frac{1}{......
  • 寒假day6 2.7
    图论割点,割边如果删去一点,整个图的连通块数量增加,即是割点。只有环上的边不是割边。tarjandfs树上不存在横叉边,只有反祖边。判断一点是否是割点对于一点,判断它的子树中是否有能连接到该点上方的返祖边。记录\(low_y\)代表子树中能回溯到的最小的dfn值。判断:\(low_n>......
  • 2024牛客寒假算法基础集训营1个人补题题解(I)
    比赛链接:2024牛客寒假算法基础集训营1I、It'sbertrandparadox.Again!这么抽象的东西出得很好,下次别再出了。从bit和buaa不同的抽数规则可以得出一个结论:bit抽取具体坐标点的次数会明显小于buaa,甚至只有在几乎不可能的理想范围内两者抽取的次数才相近,因此因为样本量极大(1e5次......
  • 牛客寒假训练赛第二场
    基本情况前面过的很顺,F吃满罚时,T4次WA4次最后乱搞过的,K有一点思路,但是码力跟不上,其他没做的题题目基本没思路。EFhttps://ac.nowcoder.com/acm/contest/67742/Ehttps://ac.nowcoder.com/acm/contest/67742/F两题虽然都是过了,但一个是提交前改了很久,一个是提交改了很久。E......