当前位置: 首页 > 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&…...

云计算——弹性云计算器(ECS)

弹性云服务器&#xff1a;ECS 概述 云计算重构了ICT系统&#xff0c;云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台&#xff0c;包含如下主要概念。 ECS&#xff08;Elastic Cloud Server&#xff09;&#xff1a;即弹性云服务器&#xff0c;是云计算…...

多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验

一、多模态商品数据接口的技术架构 &#xff08;一&#xff09;多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如&#xff0c;当用户上传一张“蓝色连衣裙”的图片时&#xff0c;接口可自动提取图像中的颜色&#xff08;RGB值&…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

优选算法第十二讲:队列 + 宽搜 优先级队列

优选算法第十二讲&#xff1a;队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

探索Selenium:自动化测试的神奇钥匙

目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...