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

CF1845 D. Rating System [思维题+数形结合]

传送门:CF

[前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下


题目很简单,不再解释.先不考虑 k k k,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化.
在这里插入图片描述
然后是一个很简单的事实:我们选取的K一定是前缀和的某一个值,更为准确的来说,应该是一个即将减少的一个前缀和值.这个结论自己把玩一下应该是不难发现的,简单的讲一下为什么是这样.因为对于一个即将减少的值来说,我们不妨选取这个值,因为这个值肯定比即将减少的那个值大,那为啥不选这个更大的值呢.而对于中间段的数来说,那些数只是中间值,两端点必然有一个点比它更为优秀.

那么现在随便选取一个端点作为我们的K,看看原图会发生什么情况
在这里插入图片描述
考虑选择的K的值为红横线.不难发现原本白色的折线因为现在K的出现需要往左上进行一个平移.
继续看蓝色的圈,我们会发现原本的平移还不够,我们需要将整个部分进行再一次平移.(因为懒所以没有进一步画出).

上面这段操作很重要,是这一道题的关键.仔细品一下上面的操作,我们就会发现后面那部分的贡献其实就是后缀最大后缀和(两个前缀和差其实就是后缀和啦),也就是当前位置开始的所有的后缀和的最大值.直接讲可能有点抽象,建议仔细看看上面的图的平移操作.数形结合一下很好理解.
PS:出现蓝圈的原因就是因为该后缀和更大.

那么这道题的解法也就呼之欲出了.考虑枚举每一个前缀和作为我们的K,然后计算一下贡献即可.

但是还存在一种特殊情况需要再仔细考虑一下:
在这里插入图片描述
对于上图的情况,我们会发现最后一段的后缀和贡献是负的,并且此时没办法进行平移.怎么解决?想一下平移的实际意义,不难发现应该令该贡献为0,也就是后缀最大值的初始值应该定义0


下面是具体的代码部分:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define ls (rt<<1)
#define rs (rt<<1|1)
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {ll x=0,w=1;char ch=getchar();for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';return x*w;
}
inline void print(__int128 x){if(x<0) {putchar('-');x=-x;}if(x>9) print(x/10);putchar(x%10+'0');
}
#define maxn 1000000
#define int long long
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
int a[maxn];int rmax[maxn],sum[maxn];
signed main() {int T=read();while(T--) {int n=read();for(int i=1;i<=n;i++) {a[i]=read();}for(int i=1;i<=n;i++) {sum[i]=sum[i-1]+a[i];}rmax[n]=0;for(int i=n-1;i>=0;i--) {rmax[i]=max(rmax[i+1],sum[n]-sum[i]);}int maxx=sum[n],ans=sum[n];for(int i=0;i<n;i++) {if(sum[i]+rmax[i]>maxx) {maxx=sum[i]+rmax[i];ans=sum[i];}	}cout<<ans<<endl;}return 0;
}

相关文章:

CF1845 D. Rating System [思维题+数形结合]

传送门:CF [前题提要]:自己在做这道题的时候思路完全想错方向,导致怎么做都做不出来,看了题解之后感觉数形结合的思考方式挺好的(或者这种做法挺典的),故写篇题解记录一下 题目很简单,不再解释.先不考虑 k k k,想想是一种什么情况?很显然应该是跟下图一样是一个折线图的变化.…...

HeidiSQL安装配置(基于小皮面板(phpstudy))连接MySQL

下载资源 对于这款图形化工具&#xff0c;博主建议通过小皮面板&#xff08;phpstudy&#xff09;来下载即可&#xff0c;也是防止你下载到钓鱼软件&#xff0c;小皮面板&#xff08;phpstudy&#xff09;如果你不懂是什么&#xff0c;请看下面链接这篇博客 第二篇&#xff1a;…...

【蓝桥2013】错误票据

错误票据 题目描述 某涉密单位下发了某种票据&#xff0c;并要在年终全部收回。 每张票据有唯一的 ID 号。全年所有票据的 ID 号是连续的&#xff0c;但 ID 的开始数码是随机选定的。 因为工作人员疏忽&#xff0c;在录入 ID 号的时候发生了一处错误&#xff0c;造成了某个…...

nvm对node版本进行管理及疑难解决,vue项目搭建与启动

一、nvm安装与node版本管理 nvm安装 1、nvm地址&#xff1a;https://github.com/coreybutler/nvm-windows/releases 2、无需配置安装包&#xff0c;nvm-setup-v1.1.10.zip 解压后双击nvm-setup.exe&#xff0c;选择安装路径&#xff0c;一路next即可 打开dos窗口输入nvm vers…...

Redisson分布式锁 原理 + 运用 记录

Redisson 分布式锁 简单入门 pom <dependency><groupId>org.redisson</groupId><artifactId>redisson</artifactId><version>3.13.6</version></dependency>配置类 package com.hmdp.config;import org.redisson.Redisson;…...

Spring Boot 笔记 021 项目部署

1.1 引入坐标&#xff0c;并双击package打包成jar包 1.2 在服务器上运行jar包 1.3 使用postman测试 2.1 运行配置 2.1.1 命令更改端口 java -jar big-event-1.0-SNAPSHOT.jar --server.port7777 2.1.2 环境变量更新&#xff08;略&#xff09; 2.1.3 外部配置文件&#xff0c…...

新技术革命开始了,Sora一出,所有的视频人、电影人都下岗

Sora一出&#xff0c;所有的视频人、电影人都下岗&#xff01; Sora直接用文本制作长达60秒的视频长镜头&#xff0c;也就是说&#xff0c;将来&#xff0c;只需要输入分镜脚本&#xff0c;电影就可以制作出来&#xff0c;不再需要几十人几百人声势浩大地去“拍”了&#xff0c…...

【FPGA开发】Modelsim和Vivado的使用

本篇文章包含的内容 一、FPGA工程文件结构二、Modelsim的使用三、Vivado的使用3.1 建立工程3.2 分析 RTL ANALYSIS3.2.1 .xdc约束&#xff08;Constraints&#xff09;文件的产生 3.3 综合 SYNTHESIS3.4 执行 IMPLEMENTATION3.5 烧录程序3.6 程序固化3.6.1 SPI约束3.6.2 .bin文…...

现代浏览器对 es模块 【esm】原生支持

现代浏览器对 ES&#xff08;ECMAScript&#xff09;模块的原生支持是指浏览器可以直接解析和执行 JavaScript 文件中的 ES 模块语法&#xff0c;无需额外的工具或转换。 具体来说&#xff0c;当浏览器遇到 import 和 export 关键字时&#xff0c;会将其识别为 ES 模块语法&…...

修改SpringBoot中默认依赖版本

例如SpringBoot2.7.2中ElasticSearch版本是7.17.4 我希望把它变成7.6.1...

网络安全最典型基础靶场-DVWA-本地搭建与初始化

写在前面&#xff1a; 之前也打过这个 DVWA 靶场&#xff0c;但是是在虚拟机环境下的一个小块分区靶场&#xff1b; 本篇博客主要介绍在本地搭建 DVWA 靶场以及靶场的初始化&#xff0c;后续会陆续更新通关教程。 由于我们是在本地搭建&#xff0c;则需要基于你已经装好 phpstu…...

算法-----高精度2(高精度乘法,高精度除法,高精度斐波那锲数列)

高精度乘法 对于高精度乘法来说似乎不像高精度加减法那样简单了&#xff0c;我们似乎得一个一个加了&#xff0c;因为我们都知道 abaaaaa…a(b个a)。如果真要这要的话那1e9*1e9不得超时啊&#xff0c;所以不能这样&#xff0c;我们还是得从乘法竖式入手 这样看似乎看不出来什…...

windows vs 自己编译源码 leveldb 然后使用自己编译的文件

1 准备源码文件 1.1 第一种方法 git下载源码 vs项目中git leveldb源码和git third_party googletest-CSDN博客 1.2 第二种方法 手动下载 然后把第三方的源码下载 复制到 third_party 对应的文件夹中 没有文件夹 third_party -> powershell mkdir third_party 2 编译lev…...

基于GPT一键完成数据分析全流程的AI Agent: Streamline Analyst

大型语言模型&#xff08;LLM&#xff09;的兴起不仅为获取知识和解决问题开辟了新的可能性&#xff0c;而且催生了一些新型智能系统&#xff0c;例如旨在辅助用户完成特定任务的AI Copilot以及旨在自动化和自主执行复杂任务的AI Agent&#xff0c;使得编程、创作等任务变得高效…...

C语言-----习题

1.通过这个例题&#xff0c;我们可以知道*p.a是无法打印99的&#xff0c;因为.的优先级比解引用*高&#xff1b; ​ struct S {int a;int b; }; int main() {struct S a, * p &a;//可以分为两部分理解//struct S a;//struct S *p &a;a.a 99;printf("%d\n"…...

Java学习笔记(五)

目录 一、控制结构 1.1 顺序控制 1.2 分支控制 &#xff08;一&#xff09;单分支 &#xff08;二&#xff09;双分支 &#xff08;三&#xff09;多分支 &#xff08;四&#xff09;嵌套分支 &#xff08;五&#xff09;switch分支 1.3 循环控制 &#xff08;一&…...

4.【Linux】进程控制(进程终止||进程等待||程序替换)

一.进程创建fork 见上篇文章 二.进程的终止 1.进程退出场景 1.代码运行完毕&#xff0c;结果正确&#xff0c;通过main函数退出码返回一般为0。 2.代码运行完毕&#xff0c;结果不正确&#xff0c;通过不同的退出码标识不同的错误原因。 3.代码异常终止&#xff08;信号&am…...

微服务设计:Spring Cloud 链路追踪概述

Spring Cloud 链路追踪是指在分布式系统中追踪请求路径的技术。它可以帮助开发者了解请求在各个微服务之间是如何流转的&#xff0c;以及每个微服务处理请求所花费的时间。链路追踪可以用于解决以下问题&#xff1a; 性能分析: 识别性能瓶颈&#xff0c;优化微服务性能。故障排…...

【MySQL/Redis】如何实现缓存一致

目录 不实用的方案 1. 先写 MySQL , 再写 Redis 2. 先写 Redis &#xff0c; 再写MySQL 3. 先删 Redis&#xff0c;再写 MySQL 实用的方案 1. 先删 Redis&#xff0c;再写 MySQL, 再删 Redis 2. 先写 MySQL , 再删 Redis 3. 先写MySQL&#xff0c;通过BinLog&#xff0…...

Socket.D 开源输传协议 v2.4.0 发布

Socket.D 协议 是基于"事件"和"语义消息""流"的网络应用层传输协议。有用户说&#xff0c;“Socket.D 之于 Socket&#xff0c;尤如 Vue 之于 Js、Mvc 之于 Http”。支持 tcp, udp, ws, kcp 传输。协议特点可参考《官网介绍》。 pyton 已开发完…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

质量体系的重要

质量体系是为确保产品、服务或过程质量满足规定要求&#xff0c;由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面&#xff1a; &#x1f3db;️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限&#xff0c;形成层级清晰的管理网络&#xf…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

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

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

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...