前后缀分离,CF1209 C. Maximal Intersection

目录

一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

二、解题报告

1、思路分析

2、复杂度

3、代码详解


一、题目

1、题目描述

2、输入输出

2.1输入

2.2输出

3、原题链接

Problem - 1029C - Codeforces


二、解题报告

1、思路分析

线段相交具有可重复贡献性:整个区间的交等价于把区间分为若干部分,分别求交再求交

那么我们只需维护每个线段的前后缀区间的线段交

然后枚举删除的线段,删除后的最大线段交就是前缀交线段和后缀交线段的交

2、复杂度

时间复杂度: O(n) 空间复杂度:O(n)

3、代码详解

import sys
from math import inf
# sys.stdin = open('in.txt', 'r')input = lambda: sys.stdin.readline().strip()
write = lambda x: sys.stdout.write(str(x))n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]prel, prer = [-inf] * n, [inf] * nfor i in range(1, n):prel[i] = max(lines[i - 1][0], prel[i - 1])prer[i] = min(lines[i - 1][1], prer[i - 1])
sufl, sufr = -inf, infans = 0for i in range(n - 1, -1, -1):ans = max(ans, min(sufr, prer[i]) - max(sufl, prel[i]))sufl = max(sufl, lines[i][0])sufr = min(sufr, lines[i][1])
write(ans)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/317157.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

预编码算法学习笔记

文章目录 1. 基本原理2. 常见应用2.1 自编码器2.2 变分自编码器2.3 稀疏自编码器 3. 学习笔记 在机器学习领域,预编码算法是一种强大的工具,用于将高维数据映射到低维表示,从而提取数据中的重要特征。本文将介绍预编码算法的基本原理、常见应…

分布式与一致性协议之拜占庭将军问题(三)

拜占庭将军问题 叛将先发送消息 如果是叛将楚先发送作战消息,干扰作战计划,结果会有所不同吗? 在第一轮作战信息协商中,楚向苏秦发送作战指令"进攻",向齐、燕发送作战指令"撤退",如图所示(当然还…

SpringCloud 学习笔记 —— 六、Ribbon:负载均衡(基于客户端)

SpringCloud 学习笔记 —— 一、背景-CSDN博客 SpringCloud 学习笔记 —— 二、微服务与微服务架构-CSDN博客 SpringCloud 学习笔记 —— 三、SpringCloud 入门概述-CSDN博客 SpringCloud 学习笔记 —— 四、SpringCloud Rest 学习环境搭建:服务提供者-CSDN博客 …

Linux 的静态库和动态库

本文目录 一、静态库1. 创建静态库2. 静态库的使用 二、动态库1. 为什么要引入动态库呢?2. 创建动态库3. 动态库的使用4. 查看可执行文件依赖的动态库 一、静态库 在编译程序的链接阶段,会将源码汇编生成的目标文件.o与引用到的库(包括静态库…

对话访谈——五问RAG与搜索引擎:探索知识检索的未来

记一次关于RAG和搜索引擎在知识检索方面的对话访谈,针对 RAG 与传统搜索引擎的异同,以及它们在知识检索领域的优劣势进行了深入的探讨。 Q:传统搜索引擎吗,通过召回-排序的两阶段模式,实现搜索逻辑的实现,当前RAG技术也…

数字旅游:通过科技赋能,创新旅游服务模式,提供智能化、个性化的旅游服务,满足游客多元化、个性化的旅游需求

目录 一、数字旅游的概念与内涵 二、科技赋能数字旅游的创新实践 1、大数据技术的应用 2、人工智能技术的应用 3、物联网技术的应用 4、云计算技术的应用 三、智能化、个性化旅游服务的实现路径 1、提升旅游服务的智能化水平 2、实现旅游服务的个性化定制 四、数字旅…

想要接触网络安全,应该怎么入门学习?

作为一个网络安全新手,首先你要明确以下几点: 我刚入门网络安全,该怎么学?要学哪些东西?有哪些方向?怎么选?这一行职业前景如何? 其次,如果你现在不清楚学什么的话&…

vim的IDE进阶之路

一 ctags 1 安装 安装ctags比较简单,我用的是vim-plug,网络上随便一搜应该就有很多教程,而且没有什么坑 2 使用 vim之函数跳转功能_nvim函数跳转-CSDN博客https://blog.csdn.net/ballack_linux/article/details/71036072不过针对cuda程序…

Java基础_集合类_List

List Collection、List接口1、继承结构2、方法 Collection实现类1、继承结构2、相关类(1)AbstractCollection(2)AbstractListAbstractSequentialList(子类) 其它接口RandomAccess【java.util】Cloneable【j…

【LAMMPS学习】八、基础知识(5.3)Body particles体粒子

8. 基础知识 此部分描述了如何使用 LAMMPS 为用户和开发人员执行各种任务。术语表页面还列出了 MD 术语,以及相应 LAMMPS 手册页的链接。 LAMMPS 源代码分发的 examples 目录中包含的示例输入脚本以及示例脚本页面上突出显示的示例输入脚本还展示了如何设置和运行各…

Go 学习笔记

Go 学习相关笔记 Go 官方的教学文档顺序不怎么友好,这里根据我自己的学习曲线来记录文档的查看顺序 基础知识 文档预备 新手先要看 Go 的模块管理介绍,这样才知道基础 Go 怎么导入外部包和进行本地的包管理 https://go.dev/doc/modules/managing-dep…

【快速入门】数据库的增删改查与结构讲解

文章的操作都是基于小皮php study的MySQL5.7.26进行演示 what 数据库是能长期存储在计算机内,有组织的,可共享的大量数据的集合。数据库中的数据按照一定的数据模型存储,具有较小的冗余性,较高的独立性和易扩展性,并为…

本地CPU搭建知识库大模型来体验学习Prompt Engineering/RAG/Agent/Text2sql

目录 1.环境 2.效果 3.概念解析 4.架构图 5. AI畅想 6.涉及到的技术方案 7. db-gpt的提示词 1.环境 基于一台16c 32G的纯CPU的机器来搭建 纯docker 打造 2.效果 3.概念解析 Prompt Engineering : 提示词工程 RAG: 检索增强生成; …

CTFHub-Web-SQL注入

CTFHub-SQL注入-WP 1.整数型注入 1.题目说输入1,先将1输入查看结果 2.接着输入4-1,发现输出的结果为4-1,判定存在整数型注入 3.查询字段数,出现了回显,判断这里的字段数为2 1 order by 24.判断注入点在2的位置&…

复杂度(3)

目录 1.二分查找的时间复杂度 2.斐波那契数列及其优化 3.空间复杂度 1.二分查找的时间复杂度 我们熟知的二分查找绝对是一种很厉害的算法,因为这个算法每进行一次都会砍掉一半的数据,相当于是指数级增长,假设我们刚开始的时候数据的个数是…

MS8241/MS8242高速、高输出电流、电压反馈放大器

产品简述 MS8241/MS8242 是一颗高速的电压反馈放大器,具有电流 反馈放大器的高速转换特性,可以应用在所有传统的电压反馈运 放应用方案中。 MS8241/MS8242 能够稳定工作在低增益环路下 (增益为 2 和 -1 ),仅消耗…

Java项目:基于SSM框架实现的实践项目管理系统(ssm+B/S架构+源码+数据库+毕业论文+开题报告)

一、项目简介 本项目是一套基于SSM框架实现的实践项目管理系统,主要针对计算机相关专业的正在做毕设的学生与需要项目实战练习的Java学习者。 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff…

【算法】【贪心算法】【leetcode】870. 优势洗牌

题目地址:https://leetcode.cn/problems/advantage-shuffle/description/ 题目描述: 给定两个长度相等的数组 nums1 和 nums2,nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。 返回 nums1 的任意排列&…

HTML5(1)

目录 一.HTML5(超文本&#xff08;链接&#xff09;标记&#xff08;标签<>&#xff09;语言) 1.开发环境&#xff08;写代码&#xff0c;看效果&#xff09; 2.vscode 使用 3.谷歌浏览器使用 4.标签语法 5.HTML基本骨架&#xff08;网页模板&#xff09; 6.标签的…

【配置】Docker搭建JSON在线解析网站

云服务器打开端口8787 连接上docker运行 docker run -id --name jsonhero -p 8787:8787 -e SESSION_SECRETabc123 henryclw/jsonhero-webhttp://ip:8787访问 Github&#xff1a;地址