【贪心】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&…...
浏览器访问 AWS ECS 上部署的 Docker 容器(监听 80 端口)
✅ 一、ECS 服务配置 Dockerfile 确保监听 80 端口 EXPOSE 80 CMD ["nginx", "-g", "daemon off;"]或 EXPOSE 80 CMD ["python3", "-m", "http.server", "80"]任务定义(Task Definition&…...
网络六边形受到攻击
大家读完觉得有帮助记得关注和点赞!!! 抽象 现代智能交通系统 (ITS) 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 (…...
服务器硬防的应用场景都有哪些?
服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式,避免服务器受到各种恶意攻击和网络威胁,那么,服务器硬防通常都会应用在哪些场景当中呢? 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...
[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...
ffmpeg(四):滤镜命令
FFmpeg 的滤镜命令是用于音视频处理中的强大工具,可以完成剪裁、缩放、加水印、调色、合成、旋转、模糊、叠加字幕等复杂的操作。其核心语法格式一般如下: ffmpeg -i input.mp4 -vf "滤镜参数" output.mp4或者带音频滤镜: ffmpeg…...
相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
【git】把本地更改提交远程新分支feature_g
创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
多种风格导航菜单 HTML 实现(附源码)
下面我将为您展示 6 种不同风格的导航菜单实现,每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...
