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
下载资源 对于这款图形化工具,博主建议通过小皮面板(phpstudy)来下载即可,也是防止你下载到钓鱼软件,小皮面板(phpstudy)如果你不懂是什么,请看下面链接这篇博客 第二篇:…...
【蓝桥2013】错误票据
错误票据 题目描述 某涉密单位下发了某种票据,并要在年终全部收回。 每张票据有唯一的 ID 号。全年所有票据的 ID 号是连续的,但 ID 的开始数码是随机选定的。 因为工作人员疏忽,在录入 ID 号的时候发生了一处错误,造成了某个…...
nvm对node版本进行管理及疑难解决,vue项目搭建与启动
一、nvm安装与node版本管理 nvm安装 1、nvm地址:https://github.com/coreybutler/nvm-windows/releases 2、无需配置安装包,nvm-setup-v1.1.10.zip 解压后双击nvm-setup.exe,选择安装路径,一路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 引入坐标,并双击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 环境变量更新(略) 2.1.3 外部配置文件,…...
新技术革命开始了,Sora一出,所有的视频人、电影人都下岗
Sora一出,所有的视频人、电影人都下岗! Sora直接用文本制作长达60秒的视频长镜头,也就是说,将来,只需要输入分镜脚本,电影就可以制作出来,不再需要几十人几百人声势浩大地去“拍”了,…...
【FPGA开发】Modelsim和Vivado的使用
本篇文章包含的内容 一、FPGA工程文件结构二、Modelsim的使用三、Vivado的使用3.1 建立工程3.2 分析 RTL ANALYSIS3.2.1 .xdc约束(Constraints)文件的产生 3.3 综合 SYNTHESIS3.4 执行 IMPLEMENTATION3.5 烧录程序3.6 程序固化3.6.1 SPI约束3.6.2 .bin文…...
现代浏览器对 es模块 【esm】原生支持
现代浏览器对 ES(ECMAScript)模块的原生支持是指浏览器可以直接解析和执行 JavaScript 文件中的 ES 模块语法,无需额外的工具或转换。 具体来说,当浏览器遇到 import 和 export 关键字时,会将其识别为 ES 模块语法&…...
修改SpringBoot中默认依赖版本
例如SpringBoot2.7.2中ElasticSearch版本是7.17.4 我希望把它变成7.6.1...
网络安全最典型基础靶场-DVWA-本地搭建与初始化
写在前面: 之前也打过这个 DVWA 靶场,但是是在虚拟机环境下的一个小块分区靶场; 本篇博客主要介绍在本地搭建 DVWA 靶场以及靶场的初始化,后续会陆续更新通关教程。 由于我们是在本地搭建,则需要基于你已经装好 phpstu…...
算法-----高精度2(高精度乘法,高精度除法,高精度斐波那锲数列)
高精度乘法 对于高精度乘法来说似乎不像高精度加减法那样简单了,我们似乎得一个一个加了,因为我们都知道 abaaaaa…a(b个a)。如果真要这要的话那1e9*1e9不得超时啊,所以不能这样,我们还是得从乘法竖式入手 这样看似乎看不出来什…...
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
大型语言模型(LLM)的兴起不仅为获取知识和解决问题开辟了新的可能性,而且催生了一些新型智能系统,例如旨在辅助用户完成特定任务的AI Copilot以及旨在自动化和自主执行复杂任务的AI Agent,使得编程、创作等任务变得高效…...
C语言-----习题
1.通过这个例题,我们可以知道*p.a是无法打印99的,因为.的优先级比解引用*高; 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 分支控制 (一)单分支 (二)双分支 (三)多分支 (四)嵌套分支 (五)switch分支 1.3 循环控制 (一&…...
4.【Linux】进程控制(进程终止||进程等待||程序替换)
一.进程创建fork 见上篇文章 二.进程的终止 1.进程退出场景 1.代码运行完毕,结果正确,通过main函数退出码返回一般为0。 2.代码运行完毕,结果不正确,通过不同的退出码标识不同的错误原因。 3.代码异常终止(信号&am…...
微服务设计:Spring Cloud 链路追踪概述
Spring Cloud 链路追踪是指在分布式系统中追踪请求路径的技术。它可以帮助开发者了解请求在各个微服务之间是如何流转的,以及每个微服务处理请求所花费的时间。链路追踪可以用于解决以下问题: 性能分析: 识别性能瓶颈,优化微服务性能。故障排…...
【MySQL/Redis】如何实现缓存一致
目录 不实用的方案 1. 先写 MySQL , 再写 Redis 2. 先写 Redis , 再写MySQL 3. 先删 Redis,再写 MySQL 实用的方案 1. 先删 Redis,再写 MySQL, 再删 Redis 2. 先写 MySQL , 再删 Redis 3. 先写MySQL,通过BinLog࿰…...
Socket.D 开源输传协议 v2.4.0 发布
Socket.D 协议 是基于"事件"和"语义消息""流"的网络应用层传输协议。有用户说,“Socket.D 之于 Socket,尤如 Vue 之于 Js、Mvc 之于 Http”。支持 tcp, udp, ws, kcp 传输。协议特点可参考《官网介绍》。 pyton 已开发完…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
消息队列系统设计与实践全解析
文章目录 🚀 消息队列系统设计与实践全解析🔍 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡💡 权衡决策框架 1.3 运维复杂度评估🔧 运维成本降低策略 🏗️ 二、典型架构设计2.1 分布式事务最终一致…...
