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

【贪心】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 题意&#xff1a; 思路&#xff1a; 首先模拟一下样例 并没有发现什么 那么就去考虑特殊情况&#xff0c;看看有没有什么启发 考虑一个大区间包含所有小区间的情形&#xff0c;这种情况就是在这么多区间中找出两个区间 换句话说&#xff0c;这么多区间组成一个…...

移动端预览指定链接的pdf文件流

场景 直接展示外部系统返回的获取文件流时出现了跨域问题&#xff1a; 解决办法 1. 外部系统返回的请求头中调整&#xff08;但是其他系统不会给你改的&#xff09; 2. 我们系统后台获取文件流并转为新的文件流提供给前端 /** 获取传入url文件流 */ GetMapping("/get…...

【Go 基础篇】Go语言字符类型:解析字符的本质与应用

介绍 字符类型是计算机编程中用于表示文本和字符的数据类型&#xff0c;是构建字符串的基本单位。在Go语言&#xff08;Golang&#xff09;中&#xff0c;字符类型具有独特的特点和表示方式&#xff0c;包括Unicode编码、字符字面值以及字符操作。本篇博客将深入探讨Go语言中的…...

Java基础(十二)面向对象编程 OOP

一、抽象数据类型 1.面向对象基本概念 1. 面向对象 面向对象程序设计&#xff08;OOP&#xff09;是一种基于对象概念的软件开发方法&#xff0c;是目前软件开发的主流方式。 常见面向对象的语言&#xff1a;C 、Python 、Java 常见面向过程的语言&#xff1a;C 面向对象的三…...

在阿里云服务器上安装Microsoft SharePoint 2016流程

本教程阿里云百科分享如何在阿里云ECS上搭建Microsoft SharePoint 2016。Microsoft SharePoint是Microsoft SharePoint Portal Server的简称。SharePoint Portal Server是一个门户站点&#xff0c;使得企业能够开发出智能的门户站点。 目录 背景信息 步骤一&#xff1a;添加…...

Ubuntu设置定时重启

1.安装/更新 cron 安装crontab sudo apt-get install cron更新命令 sudo apt-get update2.配置cron定时任务 sudo nano /etc/crontab* * * * * root reboot(从左到右&#xff0c;五个 * 依次是 分&#xff0c;时 &#xff0c;天&#xff0c;月&#xff0c;星期)下列命令表示…...

sqlloader学习笔记

INFILE的用法 1&#xff09;模糊导入多个数据的文件。 可以在文件名中使用通配符。 星号 &#xff08;*&#xff09; 表示复数字符&#xff0c;问号 &#xff08;&#xff1f;&#xff09; 表示单个字符。 INFILE emp*.dat INFILE m?emp.dat 2&#xff09;如果不需要导入数据…...

内网ip与外网ip

一、关于IP地址 我们平时直接接触最多的是内网IP。而且还可以自己手动修改ip地址。而外网ip&#xff0c;我们很少直接接触&#xff0c;都是间接接触、因为外网ip一般都是运营商管理&#xff0c;而且是全球唯一的&#xff0c;一般我们自己是无法修改的。 内网IP和外网IP是指在…...

分布式 - 消息队列Kafka:Kafka消费者和消费者组

文章目录 1. Kafka 消费者是什么&#xff1f;2. Kafka 消费者组的概念&#xff1f;3. Kafka 消费者和消费者组有什么关系&#xff1f;4. Kafka 多个消费者如何同时消费一个分区&#xff1f; 1. Kafka 消费者是什么&#xff1f; 消费者负责订阅Kafka中的主题&#xff0c;并且从…...

feign调用和被调用者字段名称不对应解决

如果您在使用Feign时&#xff0c;尝试使用SerializedName("id")或JsonAlias("id")修饰字段&#xff0c;但仍然无法正常生效&#xff0c;可能是由于以下原因&#xff1a; Feign不会直接使用Gson库进行序列化和反序列化&#xff0c;而是使用了默认的Jackson库…...

【UE4 RTS】07-Camera Boundaries

前言 本篇实现的效果是当CameraPawn移动到地图边缘时会被阻挡。 效果 步骤 1. 打开项目设置&#xff0c;在“引擎-碰撞”中&#xff0c;点击“新建Object通道” 新建通道命名为“MapBoundaries”&#xff0c;然后点击接受 2. 向视口中添加 阻挡体积 调整阻挡体积的缩放 向四…...

大语言模型之二 GPT发展史简介

得益于数据、模型结构以及并行算力的发展&#xff0c;大语言模型应用现今呈井喷式发展态势&#xff0c;大语言神经网络模型成为了不可忽视的一项技术。 GPT在自然语言处理NLP任务上取得了突破性的进展&#xff0c;扩散模型已经拥有了成为下一代图像生成模型的代表的潜力&#x…...

前后端分离------后端创建笔记(09)密码加密网络安全

本文章转载于【SpringBootVue】全网最简单但实用的前后端分离项目实战笔记 - 前端_大菜007的博客-CSDN博客 仅用于学习和讨论&#xff0c;如有侵权请联系 源码&#xff1a;https://gitee.com/green_vegetables/x-admin-project.git 素材&#xff1a;https://pan.baidu.com/s/…...

《Effects of Graph Convolutions in Multi-layer Networks》阅读笔记

一.文章概述 本文研究了在XOR-CSBM数据模型的多层网络的第一层以上时&#xff0c;图卷积能力的基本极限&#xff0c;并为它们在数据中信号的不同状态下的性能提供了理论保证。在合成数据和真实世界数据上的实验表明a.卷积的数量是决定网络性能的一个更重要的因素&#xff0c;而…...

低代码助力传统制造业数字化转型策略

随着制造强国战略逐步实施&#xff0c;制造行业数字化逐渐进入快车道。提高生产管理的敏捷性、加强产品的全生命周期质量管理是企业数字化转型的核心诉求&#xff0c;也是需要思考的核心价值。就当下传统制造业的核心问题来看&#xff0c;低代码是最佳解决方案&#xff0c;那为…...

什么叫做云计算

什么叫做云计算 相信大多数人对云计算或者是云服务的认识还停留在仅仅听过这个名词&#xff0c;但是对其真正的定义或者意义还不甚了解的层面。甚至有些技术人员&#xff0c;如果日常的业务不涉及到云服务&#xff0c;可能对其也只是一知半解的程度。首先云计算准确的讲只是云服…...

springboot 使用zookeeper实现分布式队列

一.添加ZooKeeper依赖&#xff1a;在pom.xml文件中添加ZooKeeper客户端的依赖项。例如&#xff0c;可以使用Apache Curator作为ZooKeeper客户端库&#xff1a; <dependency><groupId>org.apache.curator</groupId><artifactId>curator-framework</…...

地理数据的双重呈现:GIS与数据可视化

前一篇文章带大家了解了GIS与三维GIS的关系&#xff0c;本文就GIS话题带大家一起探讨一下GIS和数据可视化之间的关系。 GIS&#xff08;地理信息系统&#xff09;和数据可视化在地理信息科学领域扮演着重要的角色&#xff0c;它们之间密切相关且相互增强。GIS是一种用于采集、…...

Android 13 Media框架(3)- MediaPlayer生命周期

上一节了解了MediaPlayer api的使用&#xff0c;这一节就我们将会了解MediaPlayer的生命周期与api使用细节。 1、MediaPlayer生命周期 MediaPlayer.java 一开始有对生命周期的描述&#xff0c;这里对这些内容进行翻译&#xff1a; MediaPlayer 是线程不安全的&#xff0c;创建…...

[oneAPI] BERT

[oneAPI] BERT BERT训练过程Masked Language Model&#xff08;MLM&#xff09;Next Sentence Prediction&#xff08;NSP&#xff09;微调 总结基于oneAPI代码 比赛&#xff1a;https://marketing.csdn.net/p/f3e44fbfe46c465f4d9d6c23e38e0517 Intel DevCloud for oneAPI&…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

mongodb源码分析session执行handleRequest命令find过程

mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程&#xff0c;并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令&#xff0c;把数据流转换成Message&#xff0c;状态转变流程是&#xff1a;State::Created 》 St…...

前端导出带有合并单元格的列表

// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...

将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?

Otsu 是一种自动阈值化方法&#xff0c;用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理&#xff0c;能够自动确定一个阈值&#xff0c;将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

毫米波雷达基础理论(3D+4D)

3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文&#xff1a; 一文入门汽车毫米波雷达基本原理 &#xff1a;https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...