【贪心】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&…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
UE5 学习系列(三)创建和移动物体
这篇博客是该系列的第三篇,是在之前两篇博客的基础上展开,主要介绍如何在操作界面中创建和拖动物体,这篇博客跟随的视频链接如下: B 站视频:s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...
Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器
第一章 引言:语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域,文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量,支撑着搜索引擎、推荐系统、…...
华为OD机试-食堂供餐-二分法
import java.util.Arrays; import java.util.Scanner;public class DemoTest3 {public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseint a in.nextIn…...
Java求职者面试指南:计算机基础与源码原理深度解析
Java求职者面试指南:计算机基础与源码原理深度解析 第一轮提问:基础概念问题 1. 请解释什么是进程和线程的区别? 面试官:进程是程序的一次执行过程,是系统进行资源分配和调度的基本单位;而线程是进程中的…...
DingDing机器人群消息推送
文章目录 1 新建机器人2 API文档说明3 代码编写 1 新建机器人 点击群设置 下滑到群管理的机器人,点击进入 添加机器人 选择自定义Webhook服务 点击添加 设置安全设置,详见说明文档 成功后,记录Webhook 2 API文档说明 点击设置说明 查看自…...
Git 3天2K星标:Datawhale 的 Happy-LLM 项目介绍(附教程)
引言 在人工智能飞速发展的今天,大语言模型(Large Language Models, LLMs)已成为技术领域的焦点。从智能写作到代码生成,LLM 的应用场景不断扩展,深刻改变了我们的工作和生活方式。然而,理解这些模型的内部…...
Kubernetes 节点自动伸缩(Cluster Autoscaler)原理与实践
在 Kubernetes 集群中,如何在保障应用高可用的同时有效地管理资源,一直是运维人员和开发者关注的重点。随着微服务架构的普及,集群内各个服务的负载波动日趋明显,传统的手动扩缩容方式已无法满足实时性和弹性需求。 Cluster Auto…...
2.3 物理层设备
在这个视频中,我们要学习工作在物理层的两种网络设备,分别是中继器和集线器。首先来看中继器。在计算机网络中两个节点之间,需要通过物理传输媒体或者说物理传输介质进行连接。像同轴电缆、双绞线就是典型的传输介质,假设A节点要给…...
Java后端检查空条件查询
通过抛出运行异常:throw new RuntimeException("请输入查询条件!");BranchWarehouseServiceImpl.java // 查询试剂交易(入库/出库)记录Overridepublic List<BranchWarehouseTransactions> queryForReagent(Branch…...
