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 已开发完…...
单片机学习笔记---AT24C02数据存储
目录 AT24C02数据存储 准备工作 代码讲解 I2C.c 模拟起始位置的时序 模拟发送一个字节的时序 模拟接收应答的时序 模拟接收一个字节的时序 模拟发送应答的时序 模拟结束位置的时序 I2C.h AT24C02.c 字节写:在WORD ADDRESS(字地址ÿ…...
首次安装Mysql数据库
1、在mysql官网下载自己需要的版本 2、选择安装类型 3、 检查一下需求版本 4、 这里可能会弹出如下信息,先不用管这一步,点击Yes继续即可 5、 安装需要的环境,点击执行就可以,此过程会比较慢 如下就是全面安装完成了,点击next即可...
2024 前端面试题(GPT回答 + 示例代码 + 解释)No.1 - No.20
本文题目来源于全网收集,答案来源于 ChatGPT 和 博主(的小部分……) 格式:题目 h3 回答 text 参考大佬博客补充 text 示例代码 code 解释 quote 补充 quote 目录 No.1 - No.20 本文题目来源于全网收集,答案来源于…...
通过`ssh`同步`tmux`剪贴板内容
通过ssh同步tmux剪贴板内容 通过ssh连接远程服务器时,可以通过xclip同步tmux剪贴板内容。这需要在服务器上安装xclip,且需要在ssh远程连接时开启X11。 此处附tmux剪贴板调用xclip的配置: # Copy the current buffer to the system clipboa…...
HTTP 响应状态代码
HTTP 响应状态代码 HTTP 响应状态代码指示特定 HTTP 请求是否已成功完成。 响应分为五类: 信息性回复 ( 100 – 199)成功响应 ( 200 – 299)重定向消息 ( 300 – 399)客户端错误响应 ( 400 – 499)服务器错误…...
[OPEN SQL] 新增数据
INSERT语句用于数据的新增操作 本次操作使用的数据库表为SCUSTOM,其字段内容如下所示 航班用户(SCUSTOM) 该数据库表中的部分值如下所示 1.插入单条数据 语法格式 INSERT <dbtab> FROM <wa>. INSERT INTO <dbtab> VALUES <wa>. INSERT &…...
OpenHarmony—UIAbility组件生命周期
概述 当用户打开、切换和返回到对应应用时,应用中的UIAbility实例会在其生命周期的不同状态之间转换。UIAbility类提供了一系列回调,通过这些回调可以知道当前UIAbility实例的某个状态发生改变,会经过UIAbility实例的创建和销毁,…...
Mybatis的使用
MyBatis 是一个流行的 Java 持久层框架,它提供了 SQL 映射和对象关系映射的功能,让开发者能够更加便捷地操作数据库。MyBatis 通过 XML 或注解的方式配置 SQL 语句,并将 Java 对象与数据库表进行映射,以简化 JDBC 的复杂操作。以下…...
Python 播放音乐
本篇是使用Python pygame库来实现操作音乐。 安装pygame 播放音乐需要pygame库,如果没有可以进行安装。 命令如下: pip install pygame 引入类库 需要引入两个类库,即time和pygame。 示例如下: import time import pygame 播…...
[嵌入式系统-21]:RT-Thread -7- 内核组件编程接口 - 定时器
目录 一、RT-Thread定时器 1.1 概述 1.2 定时器的种类 1.2.1 周期性 1.2.2 实时性 1.2.3 功能 二、 RT-Thread 定时器的一般步骤 2.1 步骤 2.2 Flag 2.3 示例 一、RT-Thread定时器 1.1 概述 在 RT-Thread 中,定时器是一种常用的机制,用于在指…...
Python Matplotlib 的学习笔记
Python Matplotlib 的学习笔记 0. Python Matplotlib 简介1. 为什么要用 Matplotlib?2. Matplotlib 基础类详解2-1. Line(线)2-2. Marker(标记)2-3. Text(文本)2-4. Legend(图例&…...
SQL语言1
创建数据库 CREATE DATABASE 展示数据库 SHOW DATABASE 整数 INT 有小数点的数 DECIMA(m, n) #m是有几位数,n是有几位小数 字符串 VARCHAR(n) (Binary Large Object)图片 影片 BLOB ‘YYYY-MM-DD’日期 DATA YYYY-MM-DD HH:MM:SS 记…...
PowerShell搭建vue起始项目
Windows PowerShell搭建vue起始项目 搜索PowerShell,以管理员身份运行。 复制文件夹路径 cd 到这个文件夹位置 命令行创建项目:vue create 项目名 这里写自己的项目名就行,我写的yeb vue create yeb 创建成功后是这样的 有颜色的就是选中的ÿ…...
jmeter遇到连接数据库的问题
jmeter连接mysql或者oracle简单,但是连接过inceptor吗? 上货 1、下载驱动inceptor 5.1.2.jar包 2、在添加驱动那里导入 3、在JBC request中的写法 PS:没什么可说的...
应急响应实战笔记02日志分析篇(3)
第3篇:Web日志分析 ox01 Web日志 Web访问日志记录了Web服务器接收处理请求及运行时错误等各种原始信息。通过对WEB日志进行的安全分析,不仅可以帮助我们定位攻击者,还可以帮助我们还原攻击路径,找到网站存在的安全漏洞并进行修复。 我们来…...
常见性能优化策略
对于经常接触高并发服务的同学来学,会经常涉及到性能优化,但是由于平时很少总结,内容会比较分散,这里简单做一些总结 1:空间换时间 比如一些数据的访问需要很快返回结果,原本在磁盘上的数据,需…...
【微信小程序】微信小程序开发:从入门到精通
微信小程序开发:从入门到精通 一、开发准备二、小程序开发流程1、注册与创建项目2、开发页面3、配置4、调试与预览5、发布与审核 随着移动互联网的普及,微信小程序成为了越来越多企业和个人开发者的首选。小程序是一种无需下载安装即可使用的应用&#x…...
【经验】STM32的一些细节
这两天 碰到的奇葩问题是 STM32定时器同步的问题。 我的设计本意是:使用定时器T3以100us的周期来定时发送命令给 FPGA。由于编码器出结果的最长时间为51us。因此,希望PWM中断要滞后于T3 约60us 。 调试过程:分别在T3和PWM中断中置IO1&#…...
ubuntu22.04安装部署03: 设置root密码
一、前言 ubuntu22.04 安装完成以后,默认root用户是没有设置密码的,需要手动设置。具体的设置过程如下文内容所示: 相关文件: 《ubuntu22.04装部署01:禁用内核更新》 《ubuntu22.04装部署02:禁用显卡更…...
【lesson56】生产者消费者模型
文章目录 学习生产者消费者模型过程中要回答的两个问题生产者消费者模型的概念基于阻塞队列的生产者消费者模型编码实现Common.hLockGuard.hppCondtion.hppBlockQueue.hppTask.hppConProd.cc 学习生产者消费者模型过程中要回答的两个问题 1.条件变量是在条件满足的时候&#x…...
MySQL5.7升级到MySQL8.0的最佳实践分享
一、前言 事出必有因,在这个月的某个项目中,我们面临了一项重要任务,即每年一次的等保测评整改。这次测评的重点是Mysql的一些高危漏洞,客户要求我们无论如何必须解决这些漏洞。尽管我们感到无奈,但为了满足客户的要求…...
Rust 数据结构与算法:5栈:用栈实现前缀、中缀、后缀表达式
3、前缀、中缀和后缀表达式 计算机是从左到右处理数据的,类似(A (B * C))这样的完全括号表达式,计算机如何跳到内部括号计算乘法,然后跳到外部括号计算加法呢? 一种直观的方法是将运算符移到操作数外,分离运算符和操…...
作业day6
数据库 sqlite3 sq.db 如果sq.db存在则直接打开sq.db数据库,如果不存在则先创建再打开; 系统命令 需要以 . 开头,不需要以 ; 结尾 .quit 退出数据库 .exit 退出数据库 .help 显示帮助信息,获取所有系统命令; .table 查看当前数据…...
前方预警!2024年七大网络安全威胁
新颖创新技术的兴起和迅速采用已极大地改变了各行各业的全球网络安全和合规格局,比如生成式人工智能、无代码应用程序、自动化和物联网等新技术。 网络犯罪分子正转而采用新的技术、工具和软件来发动攻击,并造成更大的破坏。因此,《2023年网…...
绿色化 数据库 MongoDB 和 mysql 安装
绿色化 数据库 MongoDB 和 mysql 安装 【1.1】 前言 为什么要绿色化 安装呢?因为系统老升级,老重装!!也方便了解下数据库配置和库在那 绿色软件喜欢一般放在 D盘tools目录里 D:\tools\ 数据库 MongoDB D:\tools\MongoDB 数…...
npm install 一直卡着不动如何解决
目录 方式一:方式二: 方式一: npm cache clean --force npm config set registry https://registry.npmmirror.com npm install下面是简单的解释: 🍀1、强制清理 npm 缓存 npm cache clean --force🍀2、设…...
电路设计(15)——篮球赛24秒违例倒计时报警器的proteus仿真
1.设计要求 设计、制作一个篮球赛24秒违例倒计时报警器。要求: (1)具有倒计时功能。可完整实现从“24”秒开始依序倒计时并显示倒计时过程,显示时间间隔为1秒。 (2)具有消隐功能。当“24”秒倒计时…...
golang 集成sentry:http.Client
http.Client 是 Go 标准库 HTTP 客户端实现, sentry-go也没有这个组件,所以需要自己实现。 我们只需要对 http.Transport 进行包装即可, 完整代码如下 package mainimport ("bytes""fmt""io""log"&…...
设计链表(不难,代码稍微多一点)
设计链表 在链表类中实现这些功能: get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点。ad…...
[GXYCTF2019]禁止套娃
进来发现只有这句话,习惯性访问一下flag.php,发现不是404,那就证明flag就在这了,接下来要想办法拿到flag.php的源码。 这道题是.git文件泄露网页源码,githack拿到index.php源码 这里观察到多次判断,首先要…...