【贪心】CF1841 D
Codeforces
题意:


思路:
首先模拟一下样例

并没有发现什么
那么就去考虑特殊情况,看看有没有什么启发
考虑一个大区间包含所有小区间的情形,这种情况就是在这么多区间中找出两个区间
换句话说,这么多区间组成一个连通块,在这个连通块中找出两个区间
一个连通块贡献出两个区间
问题转化成有多少连通块
n^2枚举所有区间对,每对区间合并成一个新区间,这个新区间就是一个连通块
问题就变成在这些新区间中找最多的不相交的区间的区间个数
这个就是典,把所有新区间按 r 排序,贪心地选即可
Code:
#include <bits/stdc++.h>#define int long longusing i64 = long long;constexpr int N = 2e5 + 10;
constexpr int M = 4e6 + 10;
constexpr int mod = 998244353;struct ty {int l, r;
}a[N], b[M];int n;bool check(ty x, ty y) {return (y.l >= x.l && y.l <= x.r) || (x.l >= y.l && x.l <= y.r);
}
bool cmp(ty x, ty y) {return x.r < y.r;
}
void solve() {std::cin >> n;for (int i = 1; i <= n; i ++) {std::cin >> a[i].l >> a[i].r; }int tot = 0;for (int i = 1; i <= n; i ++) {for (int j = i + 1; j <= n; j ++) {if (check(a[i], a[j]) || check(a[j], a[i])) {b[++tot] = {std::min(a[i].l, a[j].l), std::max(a[i].r, a[j].r)};}}}if (tot == 0) {std::cout << n << "\n";return;}std::sort(b + 1, b + 1 + tot, cmp);ty t = b[1];int ans = 1;for (int i = 2; i <= tot; i ++) {if ( !check(t, b[i]) && !check(b[i], t)) {ans ++;t = b[i];}}std::cout << n - 2 * ans << "\n";
}signed main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int t = 1;std::cin >> t;while (t--) {solve();}return 0;
}
相关文章:
【贪心】CF1841 D
Codeforces 题意: 思路: 首先模拟一下样例 并没有发现什么 那么就去考虑特殊情况,看看有没有什么启发 考虑一个大区间包含所有小区间的情形,这种情况就是在这么多区间中找出两个区间 换句话说,这么多区间组成一个…...
移动端预览指定链接的pdf文件流
场景 直接展示外部系统返回的获取文件流时出现了跨域问题: 解决办法 1. 外部系统返回的请求头中调整(但是其他系统不会给你改的) 2. 我们系统后台获取文件流并转为新的文件流提供给前端 /** 获取传入url文件流 */ GetMapping("/get…...
【Go 基础篇】Go语言字符类型:解析字符的本质与应用
介绍 字符类型是计算机编程中用于表示文本和字符的数据类型,是构建字符串的基本单位。在Go语言(Golang)中,字符类型具有独特的特点和表示方式,包括Unicode编码、字符字面值以及字符操作。本篇博客将深入探讨Go语言中的…...
Java基础(十二)面向对象编程 OOP
一、抽象数据类型 1.面向对象基本概念 1. 面向对象 面向对象程序设计(OOP)是一种基于对象概念的软件开发方法,是目前软件开发的主流方式。 常见面向对象的语言:C 、Python 、Java 常见面向过程的语言:C 面向对象的三…...
在阿里云服务器上安装Microsoft SharePoint 2016流程
本教程阿里云百科分享如何在阿里云ECS上搭建Microsoft SharePoint 2016。Microsoft SharePoint是Microsoft SharePoint Portal Server的简称。SharePoint Portal Server是一个门户站点,使得企业能够开发出智能的门户站点。 目录 背景信息 步骤一:添加…...
Ubuntu设置定时重启
1.安装/更新 cron 安装crontab sudo apt-get install cron更新命令 sudo apt-get update2.配置cron定时任务 sudo nano /etc/crontab* * * * * root reboot(从左到右,五个 * 依次是 分,时 ,天,月,星期)下列命令表示…...
sqlloader学习笔记
INFILE的用法 1)模糊导入多个数据的文件。 可以在文件名中使用通配符。 星号 (*) 表示复数字符,问号 (?) 表示单个字符。 INFILE emp*.dat INFILE m?emp.dat 2)如果不需要导入数据…...
内网ip与外网ip
一、关于IP地址 我们平时直接接触最多的是内网IP。而且还可以自己手动修改ip地址。而外网ip,我们很少直接接触,都是间接接触、因为外网ip一般都是运营商管理,而且是全球唯一的,一般我们自己是无法修改的。 内网IP和外网IP是指在…...
分布式 - 消息队列Kafka:Kafka消费者和消费者组
文章目录 1. Kafka 消费者是什么?2. Kafka 消费者组的概念?3. Kafka 消费者和消费者组有什么关系?4. Kafka 多个消费者如何同时消费一个分区? 1. Kafka 消费者是什么? 消费者负责订阅Kafka中的主题,并且从…...
feign调用和被调用者字段名称不对应解决
如果您在使用Feign时,尝试使用SerializedName("id")或JsonAlias("id")修饰字段,但仍然无法正常生效,可能是由于以下原因: Feign不会直接使用Gson库进行序列化和反序列化,而是使用了默认的Jackson库…...
【UE4 RTS】07-Camera Boundaries
前言 本篇实现的效果是当CameraPawn移动到地图边缘时会被阻挡。 效果 步骤 1. 打开项目设置,在“引擎-碰撞”中,点击“新建Object通道” 新建通道命名为“MapBoundaries”,然后点击接受 2. 向视口中添加 阻挡体积 调整阻挡体积的缩放 向四…...
大语言模型之二 GPT发展史简介
得益于数据、模型结构以及并行算力的发展,大语言模型应用现今呈井喷式发展态势,大语言神经网络模型成为了不可忽视的一项技术。 GPT在自然语言处理NLP任务上取得了突破性的进展,扩散模型已经拥有了成为下一代图像生成模型的代表的潜力&#x…...
前后端分离------后端创建笔记(09)密码加密网络安全
本文章转载于【SpringBootVue】全网最简单但实用的前后端分离项目实战笔记 - 前端_大菜007的博客-CSDN博客 仅用于学习和讨论,如有侵权请联系 源码:https://gitee.com/green_vegetables/x-admin-project.git 素材:https://pan.baidu.com/s/…...
《Effects of Graph Convolutions in Multi-layer Networks》阅读笔记
一.文章概述 本文研究了在XOR-CSBM数据模型的多层网络的第一层以上时,图卷积能力的基本极限,并为它们在数据中信号的不同状态下的性能提供了理论保证。在合成数据和真实世界数据上的实验表明a.卷积的数量是决定网络性能的一个更重要的因素,而…...
低代码助力传统制造业数字化转型策略
随着制造强国战略逐步实施,制造行业数字化逐渐进入快车道。提高生产管理的敏捷性、加强产品的全生命周期质量管理是企业数字化转型的核心诉求,也是需要思考的核心价值。就当下传统制造业的核心问题来看,低代码是最佳解决方案,那为…...
什么叫做云计算
什么叫做云计算 相信大多数人对云计算或者是云服务的认识还停留在仅仅听过这个名词,但是对其真正的定义或者意义还不甚了解的层面。甚至有些技术人员,如果日常的业务不涉及到云服务,可能对其也只是一知半解的程度。首先云计算准确的讲只是云服…...
springboot 使用zookeeper实现分布式队列
一.添加ZooKeeper依赖:在pom.xml文件中添加ZooKeeper客户端的依赖项。例如,可以使用Apache Curator作为ZooKeeper客户端库: <dependency><groupId>org.apache.curator</groupId><artifactId>curator-framework</…...
地理数据的双重呈现:GIS与数据可视化
前一篇文章带大家了解了GIS与三维GIS的关系,本文就GIS话题带大家一起探讨一下GIS和数据可视化之间的关系。 GIS(地理信息系统)和数据可视化在地理信息科学领域扮演着重要的角色,它们之间密切相关且相互增强。GIS是一种用于采集、…...
Android 13 Media框架(3)- MediaPlayer生命周期
上一节了解了MediaPlayer api的使用,这一节就我们将会了解MediaPlayer的生命周期与api使用细节。 1、MediaPlayer生命周期 MediaPlayer.java 一开始有对生命周期的描述,这里对这些内容进行翻译: MediaPlayer 是线程不安全的,创建…...
[oneAPI] BERT
[oneAPI] BERT BERT训练过程Masked Language Model(MLM)Next Sentence Prediction(NSP)微调 总结基于oneAPI代码 比赛:https://marketing.csdn.net/p/f3e44fbfe46c465f4d9d6c23e38e0517 Intel DevCloud for oneAPI&…...
(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)
题目:3442. 奇偶频次间的最大差值 I 思路 :哈希,时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况,哈希表这里用数组即可实现。 C版本: class Solution { public:int maxDifference(string s) {int a[26]…...
大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)
一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解,适合用作学习或写简历项目背景说明。 🧠 一、概念简介:Solidity 合约开发 Solidity 是一种专门为 以太坊(Ethereum)平台编写智能合约的高级编…...
JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作
一、上下文切换 即使单核CPU也可以进行多线程执行代码,CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短,所以CPU会不断地切换线程执行,从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
SiFli 52把Imagie图片,Font字体资源放在指定位置,编译成指定img.bin和font.bin的问题
分区配置 (ptab.json) img 属性介绍: img 属性指定分区存放的 image 名称,指定的 image 名称必须是当前工程生成的 binary 。 如果 binary 有多个文件,则以 proj_name:binary_name 格式指定文件名, proj_name 为工程 名&…...
MinIO Docker 部署:仅开放一个端口
MinIO Docker 部署:仅开放一个端口 在实际的服务器部署中,出于安全和管理的考虑,我们可能只能开放一个端口。MinIO 是一个高性能的对象存储服务,支持 Docker 部署,但默认情况下它需要两个端口:一个是 API 端口(用于存储和访问数据),另一个是控制台端口(用于管理界面…...
通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器
拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件: 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...
