当前位置: 首页 > news >正文

Maximum Sum(贪心策略,模运算,最大子段和)

文章目录

  • 题目描述
    • 输入格式
    • 输出格式
    • 样例输入1
    • 样例输出1
    • 样例输入2
    • 样例输出2
    • 提交链接
    • 提示
  • 解析
  • 参考代码

题目描述

你有一个由 n n n 个整数组成的数组 a a a

你要对它进行 k k k 次操作。其中一个操作是选择数组 a a a 的任意连续子数组(可能为空),并在数组的任意位置插入该子数组的和。

你的任务是找出 k k k 次这样的操作后数组可能的最大和。

由于这个数字可能非常大,请输出取模为 1 0 9 + 7 10^9+7 109+7 的答案。

提示:数字 x m o d p x\mod\ p xmod p 的余数等于最小非负数 y y y,满足 x = p ⋅ q + y x=p⋅q+y x=pq+y ( q q q 为整数)。

输入格式

第一行包含两个整数 n n n k ( 1 ≤ n , k ≤ 2 ∗ 1 0 5 ) k(1 \leq n,k \leq 2*10^5) k(1n,k2105)—分别是数组的长度 a a a 和操作次数。

第二行包含 n n n 个整数 a 1 , a 2 , . . . , a n ( − 1 0 9 ≤ a i ≤ 1 0 9 ) a_1,a_2,...,a_n(-10^9 \leq a_i \leq 10^9) a1,a2,...,an(109ai109)

输出格式

输出一个整数—经过 k k k 次运算模数 1 0 9 + 7 10^9+7 109+7 后得到的数组最大和。

样例输入1

2 2
-4 -7

样例输出1

999999996

样例输入2

3 3
2 2 8

样例输出2

96

提交链接

https://hydro.ac/d/lp728/p/13

提示

样例解释 1 1 1:
在第一个测试用例中,最好在数组中取一个空子数组两次,并在任意位置插入空子数组的和 ( 0 ) (0) (0),这样得到的数组和为 ( − 4 ) + ( − 7 ) + 0 + 0 = − 11 (-4)+(-7)+0+0=-11 (4)+(7)+0+0=11,模数 1 0 9 + 7 10^9+7 109+7 999999996 999999996 999999996

解析

核心:找到数组中总和最大的子数组。

s s s 表示为原始数组的总和, x x x 表示为原始数组中总和最大的子数组的总和。
k = 1 k=1 k=1 时,答案为 s + x s+x s+x k = 2 k=2 k=2 时,答案为 s + x + 2 ∗ x s+x+2*x s+x+2x

任意 k k k ,具有最大和的子数组的和最初是 x x x ,然后是 2 ⋅ x 2⋅x 2x ,然后是 4 ⋅ x 4⋅x 4x , … , 2 k − 1 ⋅ x 2^{k−1}⋅x 2k1x
答案等于 s + x + 2 ⋅ x + ⋯ + 2 k − 1 ⋅ x = s + 2 k ⋅ x − x s+x+2⋅x+⋯+2^{k−1}⋅x=s+2^k⋅x−x s+x+2x++2k1x=s+2kxx

取余的时候要考虑负数的情况。若为负数可以先加上模数再进行取余。

参考代码

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
const int maxn = 2e5 + 9 , mod = 1e9 + 7;
typedef long long ll;
int t , n , a[maxn] , k;
int main()
{ll ans = 0;cin >> n >> k;for(int i = 1; i <= n; i++){cin >> a[i];ans += a[i];}ans = (ans % mod + mod) % mod;ll sum = 0 , mx = 0;for(int i = 1; i <= n; i++)  //区间最大和{sum += a[i];if(sum < 0)sum = 0;mx = max(mx , sum);}mx %= mod;ll two = 1;for(int i = 1; i <= k; i++)two = two * 2 % mod;ans = (ans + two * mx - mx + mod) % mod;cout << ans << endl;return 0;
}

相关文章:

Maximum Sum(贪心策略,模运算,最大子段和)

文章目录 题目描述输入格式输出格式样例输入1样例输出1样例输入2样例输出2提交链接提示 解析参考代码 题目描述 你有一个由 n n n 个整数组成的数组 a a a 。 你要对它进行 k k k 次操作。其中一个操作是选择数组 a a a 的任意连续子数组(可能为空)&#xff0c;并在数组的…...

Gartner 公布 2024 年八大网络安全预测

近日&#xff0c;Gartner 安全与风险管理峰会在悉尼举行&#xff0c;旨在探讨网络安全的发展前景。 本次峰会&#xff0c;Gartner 公布了 2024 年及以后的八大网络安全预测。 Gartner 研究总监 Deepti Gopal 表示&#xff0c;随着 GenAI 的不断发展&#xff0c;一些长期困扰网…...

《每天十分钟》-红宝书第4版-对象、类与面向对象编程(六)

盗用构造函数 上节提到原型包含引用值导致的继承问题&#xff0c;为了解决这种问题&#xff0c;一种叫作“盗用构造函数”&#xff08;constructor stealing&#xff09;的技术在开发社区流行起来&#xff08;这种技术有时也称作“对象伪装”或“经典继承”&#xff09;。基本…...

Ubuntu Desktop Server - user 用户与 root 用户切换

Ubuntu Desktop Server - user 用户与 root 用户切换 1. user 用户与 root 用户切换2. root 用户与 user 用户切换References 1. user 用户与 root 用户切换 strongforeverstrong:~$ strongforeverstrong:~$ sudo su [sudo] password for strong: rootforeverstrong:/home/s…...

SQL Server事务复制操作出现的错误 进程无法在“xxx”上执行sp_replcmds

SQL Server事务复制操作出现的错误 进程无法在“xxx”上执行“sp_replcmds” 无法作为数据库主体执行&#xff0c;因为主体 "dbo" 不存在、无法模拟这种类型的主体&#xff0c;或您没有所需的权限...

学点儿Java_Day12_IO流

1 IO介绍以及分类 IO: Input Output 流是一组有顺序的&#xff0c;有起点和终点的字节集合&#xff0c;是对数据传输的总称或抽象。即数据在两设备间的传输称为流&#xff0c;流的本质是数据传输&#xff0c;根据数据传输特性将流抽象为各种类&#xff0c;方便更直观的进行数据…...

【python】python编程初探1----python中的基本语法,标识符,关键字,注释,多行书写,代码缩进,语句块,模块等

欢迎来CILMY23的博客喔&#xff0c;本篇为【python】python编程初探1----python中的基本语法&#xff0c;标识符&#xff0c;关键字&#xff0c;注释&#xff0c;多行书写&#xff0c;代码缩进&#xff0c;语句块&#xff0c;模块&#xff0c;感谢观看&#xff0c;支持的可以给…...

牛客周赛 Round 38

牛客竞赛_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com) A-小红的正整数自增_牛客周赛 Round 38 (nowcoder.com) 取出最后一位判断即可 #include<iostream> #include<algorithm> #include<vector> #include<set> #include…...

漏洞扫描操作系统识别技术原理

漏洞扫描过程中&#xff0c;操作系统识别技术是至关重要的一步&#xff0c;因为它有助于扫描器针对性地选择适用的漏洞检测规则&#xff0c;提高扫描的准确性和效率。以下是漏洞扫描中操作系统识别技术的主要原理&#xff1a; **1. **TCP/IP 协议栈指纹识别** **原理**&#…...

数据结构与算法-分治算法

数据结构与算法 数据结构与算法是计算机科学中的两个核心概念&#xff0c;它们在软件开发和问题解决中起着至关重要的作用。 数据结构 数据结构是计算机中存储、组织和管理数据的方式&#xff0c;它能够帮助我们高效地访问和修改数据。不同的数据结构适用于不同类型的应用场…...

MNN详细介绍、安装和编译

目录 第一章:MNN简介 1.1、MNN概述 1.2、MNN特点 1.3、MNN在移动端的应用优势 第二章:MNN安装与配置 2.1、环境准备 2.2、下载与编译 第三章:MNN使用指南 3.1、模型转换与部署 3.2、推理示例 第四章:MNN高级应用与优化技巧...

uniapp-Form示例(uviewPlus)

示例说明 Vue版本&#xff1a;vue3 组件&#xff1a;uviewPlus&#xff08;Form 表单 | uview-plus 3.0 - 全面兼容nvue的uni-app生态框架 - uni-app UI框架&#xff09; 说明&#xff1a;表单组建、表单验证、提交验证等&#xff1b; 截图&#xff1a; 示例代码 <templat…...

【Linux】详解进程程序替换

一、替换原理 用fork创建子进程后执行的是和父进程相同的程序(但有可能执行不同的代码分支)&#xff0c;子进程往往要调用一种exec函数以执行另一个程序。当进程调用一种exec函数时&#xff0c;该进程的用户空间代码和数据完全被新程序替换&#xff0c;从新程序的启动例程开始执…...

vue中使用jsmind生成脑图

项目部分参数&#xff1a; vue&#xff1a;2.6.10 node:16.20.0 1、使用命令行安装jsmind&#xff1a; npm i jsmind -S 2、在文件中引入jsmind&#xff0c;并编写渲染jsmind的代码&#xff1a;&#xff1a; <template><!-- jsmind容器 --><divid"jsmi…...

yarn按包的时候报错 ../../../package.json: No license field

运行 yarn config list 然后运行 yarn config set strict-ssl false 之后yarn就成功了...

【Python从入门到进阶】51、电影天堂网站多页面下载实战

接上篇《50、当当网Scrapy项目实战&#xff08;三&#xff09;》 上一篇我们讲解了使用Scrapy框架在当当网抓取多页书籍数据的效果&#xff0c;本篇我们来抓取电影天堂网站的数据&#xff0c;同样采用Scrapy框架多页面下载的模式来实现。 一、抓取需求 打开电影天堂网站&…...

苹果CMS影视APP源码,二开版本带视频教程

编译app教程 工具下载&#xff1a;Android Studio 官网地址&#xff1a;https://developer.android.google.cn/studio/ 环境设置&#xff1a; 设置中文&#xff1a;https://blog.csdn.net/qq_37131111/article/details/131492844 汉化包找最新的下载就行了&#xff0c;随便下载…...

Zigbee技术在智能农业领域的应用研究

Zigbee技术在智能农业领域的应用研究 **摘要&#xff1a;**随着现代信息技术的飞速发展&#xff0c;智能农业已成为当今农业发展的新趋势。Zigbee技术作为一种低功耗、低成本的无线通信技术&#xff0c;在智能农业领域具有广泛的应用前景。本文深入分析了Zigbee技术的原理和特…...

Spring Cloud Gateway 中GET请求能正常访问,POST请求出现Unable to handle DataBuffer

报错信息如下&#xff1a; java.lang.IllegalArgumentException: Unable to handle DataBuffer of type class org.springframework.http.server.reactive.UndertowServerHttpRequest$UndertowDataBufferat org.springframework.cloud.gateway.filter.NettyRoutingFilter.getB…...

什么是git? 初步认识git 如何使用git

Git是什么&#xff1f; Git 是分布式版本控制系统&#xff0c;可以有效&#xff0c;高速地处理从很小到非常大地项目版本管理&#xff0c;分布式相比于集中式的最大区别在于开发者可以提交到本地&#xff0c;每个开发者可以通过克隆&#xff0c;在本地机器上拷贝一个完整的Git …...

IDEA运行Tomcat出现乱码问题解决汇总

最近正值期末周&#xff0c;有很多同学在写期末Java web作业时&#xff0c;运行tomcat出现乱码问题&#xff0c;经过多次解决与研究&#xff0c;我做了如下整理&#xff1a; 原因&#xff1a; IDEA本身编码与tomcat的编码与Windows编码不同导致&#xff0c;Windows 系统控制台…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

使用分级同态加密防御梯度泄漏

抽象 联邦学习 &#xff08;FL&#xff09; 支持跨分布式客户端进行协作模型训练&#xff0c;而无需共享原始数据&#xff0c;这使其成为在互联和自动驾驶汽车 &#xff08;CAV&#xff09; 等领域保护隐私的机器学习的一种很有前途的方法。然而&#xff0c;最近的研究表明&…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

HBuilderX安装(uni-app和小程序开发)

下载HBuilderX 访问官方网站&#xff1a;https://www.dcloud.io/hbuilderx.html 根据您的操作系统选择合适版本&#xff1a; Windows版&#xff08;推荐下载标准版&#xff09; Windows系统安装步骤 运行安装程序&#xff1a; 双击下载的.exe安装文件 如果出现安全提示&…...

基于Docker Compose部署Java微服务项目

一. 创建根项目 根项目&#xff08;父项目&#xff09;主要用于依赖管理 一些需要注意的点&#xff1a; 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件&#xff0c;否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

【论文阅读28】-CNN-BiLSTM-Attention-(2024)

本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...