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

前缀和算法-截断数组

 5057. 截断数组 - AcWing题库

给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。

现在,要将该数组从中间截断,得到两个非空子数组。

我们规定,一个数组的价值等于数组内所有元素之和模 p 的结果。

我们希望,将给定数组截断后,得到的两个非空子数组的价值之和尽可能大。

请你输出这两个非空子数组的价值之和的最大可能值。

输入格式

第一行包含两个整数 n 和 p。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数,表示价值之和的最大可能值。

数据范围

前 33 个测试点满足 2≤n≤10。
所有测试点满足 2≤n≤105,2≤p≤10000,1≤ai≤106。

输入样例1:
4 10
3 4 7 2
输出样例1:
16
输入样例2:
10 12
16 3 24 13 9 8 7 5 12 12
输出样例2:
13

题意是找到一个点x,然后求 1到x 的区间和加上 x+1到n 的区间和最大,所以只需要遍历 x 的位置,就是1到n,然后根据前缀和算法O(1)得到区间和即可

AC ode:

#include<bits/stdc++.h>
using namespace std;
int arr[100010];
long long s[100010];
long long ans = -1;
int p, n;
int main() {cin >> n >> p;for (int i = 1; i <= n; i++) {cin >> arr[i];s[i] = s[i - 1] + arr[i];}for (int i = 1; i <= n - 1; i++) {long long l = s[i] % p;long long r = (s[n] - s[i]) % p;long long x = l + r;ans = max(ans, x);}cout << ans;
}

相关文章:

前缀和算法-截断数组

5057. 截断数组 - AcWing题库 给定一个长度为 n 的正整数数组 a1,a2,…,an 和一个正整数 p。 现在&#xff0c;要将该数组从中间截断&#xff0c;得到两个非空子数组。 我们规定&#xff0c;一个数组的价值等于数组内所有元素之和模 p 的结果。 我们希望&#xff0c;将给定数组…...

Kubernetes实战:Kubernetes中网络插件calico Daemon Sets显示异常红色

目录 一、排查步骤与解决方案1.1、POD排查问题定位1.2、针对问题解决错误1.3、继续针对问题解决错误 一、排查步骤与解决方案 1.1、POD排查问题定位 我的k8s集群由3个节点组成的&#xff0c;calico在每个节点上都有一个pod,通过kubectl get pod -A命令发现有一个pod的READY 为…...

深入探究:JSONCPP库的使用与原理解析

君子不器 &#x1f680;JsonCPP开源项目直达链接 文章目录 简介Json示例小结 JsoncppJson::Value序列化Json::Writer 类Json::FastWriter 类Json::StyledWriter 类Json::StreamWriter 类Json::StreamWriterBuilder 类示例 反序列化Json::Reader 类Json::CharReader 类Json::Ch…...

字节UC伯克利新研究 | Magic-Me:简单有效的主题ID可控视频生成框架

在生成模型领域&#xff0c;针对特定身份&#xff08;ID&#xff09;创建内容已经引起了极大的兴趣。在文本到图像生成&#xff08;T2I&#xff09;领域&#xff0c;以主题驱动的内容生成已经取得了巨大的进展&#xff0c;使图像中的ID可控。然而&#xff0c;将其扩展到视频生成…...

2024免费人像摄影后期处理工具Portraiture4.1

Portraiture作为一款智能磨皮插件&#xff0c;确实为Photoshop和Lightroom用户带来了极大的便利。通过其先进的人工智能算法&#xff0c;它能够自动识别并处理照片中的人物皮肤、头发和眉毛等部位&#xff0c;实现一键式的磨皮美化效果&#xff0c;极大地简化了后期处理的过程。…...

Spring Boot 笔记 010 创建接口_更新用户头像

1.1.1 usercontroller中添加updateAvatar&#xff0c;校验是否为url PatchMapping("updateAvatar")public Result updateAvatar(RequestParam URL String avatarUrl) {userService.updateAvatar(avatarUrl);return Result.success();} 1.1.2 userservice //更新头像…...

认识并使用HttpLoggingInterceptor

目录 一、前情回顾二、HttpLoggingInterceptor1、HttpLoggingInterceptor拦截器是做什么的&#xff1f;2、如何使用HttpLoggingInterceptor&#xff1f;2.1 日志级别2.2 如何看日志&#xff1f;2.2.1 日志级别&#xff1a;BODY2.2.2 日志级别&#xff1a;BASIC2.2.3 日志级别&a…...

内存块与内存池

&#xff08;1&#xff09;在运行过程中&#xff0c;MemoryPool内存池可能会有多个用来满足内存申请请求的内存块&#xff0c;这些内存块是从进程堆中开辟的一个较大的连续内存区域&#xff0c;它由一个MemoryBlock结构体和多个可供分配的内存单元组成&#xff0c;所有内存块组…...

【FPGA开发】HDMI通信协议解析及FPGA实现

本篇文章包含的内容 一、HDMI简介1.1 HDMI引脚解析1.2 HDMI工作原理1.3 DVI编码1.4 TMDS编码 二、并串转换、单端差分转换原语2.1 原语简介2.2 原语&#xff1a;IO端口组件2.3 IOB 输入输出缓冲区2.4 并转串原语OSERDESE22.4.1 OSERDESE2 工作原理2.4.2 OSERDESE2 级联示意图2.…...

[NSSRound#16 Basic]Web

1.RCE但是没有完全RCE 显示md5强比较&#xff0c;然后md5_3随便传 md5_1M%C9h%FF%0E%E3%5C%20%95r%D4w%7Br%15%87%D3o%A7%B2%1B%DCV%B7J%3D%C0x%3E%7B%95%18%AF%BF%A2%00%A8%28K%F3n%8EKU%B3_Bu%93%D8Igm%A0%D1U%5D%83%60%FB_%07%FE%A2&md5_2M%C9h%FF%0E%E3%5C%20%95r%D4w…...

[职场] 会计学专业学什么 #其他#知识分享#职场发展

会计学专业学什么 会计学专业属于工商管理学科下的一个二级学科&#xff0c;本专业培养具备财务、管理、经济、法律等方面的知识和能力&#xff0c;具有分析和解决财务、金融问题的基本能力&#xff0c;能在企、事业单位及政府部门从事会计实务以及教学、科研方面工作的工商管…...

docker (五)-docker存储-数据持久化

将数据存储在容器中&#xff0c;一旦容器被删除&#xff0c;数据也会被删除。同时也会使容器变得越来越大&#xff0c;不方便恢复和迁移。 将数据存储到容器之外&#xff0c;这样删除容器也不会丢失数据。一旦容器故障&#xff0c;我们可以重新创建一个容器&#xff0c;将数据挂…...

飞行路线(分层图+dijstra+堆优化)(加上题目选数复习)

飞行路线 这一题除了堆优化和dijstra算法和链式前向星除外还多考了一个考点就是&#xff0c;分层图&#xff0c;啥叫分层图呢&#xff1f;简而言之就是一个三维的图&#xff0c;按照其题意来说有几个可以免费的点就有几层&#xff0c;而且这个分层的权值为0&#xff08;这样就相…...

云计算基础-快照与克隆

快照及克隆 什么是快照 快照是数据存储的某一时刻的状态记录&#xff0c;也就是把虚拟机当前的状态保存下来(快照不是备份&#xff0c;快照保存的是状态&#xff0c;备份保存的是副本) 快照优点 速度快&#xff0c;占用空间小 快照工作原理 在了解快照原理前&#xff0c;…...

使用 RAG 创建 LLM 应用程序

如果您考虑为您的文件或网站制作一个能够回应您的个性化机器人&#xff0c;那么您来对地方了。我可以帮助您使用Langchain和RAG策略来创建这样一个机器人。 了解ChatGPT的局限性和LLMs ChatGPT和其他大型语言模型&#xff08;LLMs&#xff09;经过广泛训练&#xff0c;以理解…...

第13章 网络 Page744~746 asio核心类 ip::tcp::endPoint

2. ip::tcp::endpoint ip::tcp::socket用于连接TCP服务端的 async_connect()方法的第一个入参是const endpoint_type& peer_endpoint. 此处的类型 endpoint_type 是 ip::tcp::endpoint 在 在 ip::tcp::socket 类内部的一个别名。 libucurl 库采用字符串URL表达目标的地…...

面试浏览器框架八股文十问十答第一期

面试浏览器框架八股文十问十答第一期 作者&#xff1a;程序员小白条&#xff0c;个人博客 相信看了本文后&#xff0c;对你的面试是有一定帮助的&#xff01;关注专栏后就能收到持续更新&#xff01; ⭐点赞⭐收藏⭐不迷路&#xff01;⭐ 1&#xff09;什么是 XSS 攻击&#…...

多线程的基本原理学习

由一个问题引发的思考 线程的合理使用能够提升程序的处理性能&#xff0c;主要有两个方面&#xff0c;第一个是能够利用多核cpu以及超线程技术来实现线程的并行执行&#xff1b;第二个是线程的异步化执行相比于同步执行来说&#xff0c;异步执行能够很好的优化程序的处理性能提…...

C/C++进制转换

十进制转化为二进制 进制转化#include <iostream> using namespace std;void change(int); int main() {int num;cout << "请输入一个十进制数: ";cin >> num;cout << "转化后的二进制数为: ";change(num);return 0; } void chan…...

使用 Coze 搭建 TiDB 助手

导读 本文介绍了使用 Coze 平台搭建 TiDB 文档助手的过程。通过比较不同 AI Bot 平台&#xff0c;突出了 Coze 在插件能力和易用性方面的优势。文章深入讨论了实现原理&#xff0c;包括知识库、function call、embedding 模型等关键概念&#xff0c;最后成功演示了如何在 Coze…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

超短脉冲激光自聚焦效应

前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应&#xff0c;这是一种非线性光学现象&#xff0c;主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场&#xff0c;对材料产生非线性响应&#xff0c;可能…...

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

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

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

【配置 YOLOX 用于按目录分类的图片数据集】

现在的图标点选越来越多&#xff0c;如何一步解决&#xff0c;采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集&#xff08;每个目录代表一个类别&#xff0c;目录下是该类别的所有图片&#xff09;&#xff0c;你需要进行以下配置步骤&#x…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...