Fancy 的区间(C++)(前缀和差分)
目录
1.题目描述
2.AC
1.题目描述
Fancy 的区间
时间限制: 1.000 Sec 内存限制: 128 MB
题目描述
省选终于考完了,但是还是不出成绩,Fancy 非常焦急而忧伤的等待着。
闲着无聊的 Fancy 打开书包拿出了一张纸和一支笔,在纸上画了一行n个格子。Fancy 每次想两个数字,然后把这两个数字之间(包括这两个数字)的格子涂黑。如果有格子已经涂过了,Fancy 还会再涂一遍(反正都是黑的)。突然成绩出来了,Fancy 跑去听成绩了,不小心把纸掉在了地上。现在 Fancy 想知道还有哪些区间没有涂黑,你能帮帮她吗?
输入
第一行两个数n和 m,n表示格子数目,m表示区间对数。 接下来m行,每行两个数x和y,表示将x 到y之间的格子涂黑。
输出
输出若干行,每一行两个数x和 y,中间用空格隔开,表示从x到 y 之间是白色的。
注:
1.从x到 y 表示包括x和 y 的中间一整段;
2.输出的区间必须合法(x≤y)且无重复;
3.如果只有一个点x,则输出 x x;
4.输出时区间按左端点排序,且不允许出现前后两个区间可以合并的情况,如 1 3 和 4 5 要输出 1 5;
5.若所有区间都被覆盖,则不用输出;
样例输入 Copy
10 3
1 3
2 5
8 9
样例输出 Copy
6 7
10 10
提示
对于100%的数据,1≤n≤1000000,1≤m≤500000,1≤x≤y≤n。
标签
差分,前缀和,模拟
2.AC
#include <iostream>
#include <cstdio>
using namespace std;
int n, m, ans = 0;
int b[1000005];
int main () {scanf ("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int l, r;scanf ("%d%d", &l, &r);b[l] += 1;b[r+1] -= 1;}for (int i = 1; i <= n; i++) {b[i] += b[i-1];}b[n+1] = 1;int x = 0;for (int i = 1; i <= n; i++) {if (!b[i]&&b[i+1]) {if (!x) printf ("%d %d\n", i, i);else printf("%d %d\n", x, i);x = 0;} else if (!b[i]&&!b[i+1]&&!x) {x = i;}}if (x) printf("%d %d", x, n);return 0;
}
相关文章:
Fancy 的区间(C++)(前缀和差分)
目录 1.题目描述 2.AC 1.题目描述 Fancy 的区间 时间限制: 1.000 Sec 内存限制: 128 MB 题目描述 省选终于考完了,但是还是不出成绩,Fancy 非常焦急而忧伤的等待着。 闲着无聊的 Fancy 打开书包拿出了一张纸和一支笔,在纸上画了一行n个…...
06 【Sass语法介绍-函数】
这篇文章只更新了颜色函数,由于Sass使用时间过短,其它函数参考官网 1.前言 Sass 中的函数,这在 Sass 中是比较强大的一个功能,同时使用场景和语法也比较多,所以本节内容篇幅较长,但你一定要好好学习&#…...
入参校验产品化 schema
与规则引擎不同,规则面向技术, 传入data, 返回 所有异常字段和原因. 面向技术, 先有对象,再有规则, 如何通过交互来编写schema是个难题? 和json-schema区别: 思路上就是反过来的, 面相产品, schema可视化编辑器, 是面向结构设计. 现有模型,才有数据, 才可以编程. 基于配置…...
【Linux】7、一篇文章学习 Linux 中一些硬核的常用知识
目录 一、systemctl二、软链接三、日期(date 命令)四、Linux 的时区(1) 修改时区(2) ntp 五、IP 地址六、主机名七、域名解析八、配置 Linux 的固定 IP 地址(1) 在 VMwareWorkstation 中配置 IP 地址网关和网段(IP 地址的范围)(2)…...
gpt4-如何使用
gpt-4怎么用 目前,GPT-4尚未发布或公开释放。因此,我们目前无法使用GPT-4。GPT-4是由OpenAI公司开发的人工智能语言模型,其预计能够比先前的版本GPT-3更加强大和智能化,但我们需要等待OpenAI官方发布有关GPT-4的更多信息。 如果您…...
定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现?
定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现? 可以使用linux的计划任务功能crontab来实现定时执行脚本。 具体步骤如下: 编辑crontab计划任务列表: bash crontab -e 这会打开一个文本编辑器,你可以在里面添加计划任务。添加一行计划任务,内容如…...
C++ 设计模式23:访问者模式
C++ 23种设计模式系列文章目录 创建型模式 第1式 工厂方法模式 第2式 抽象工厂模式 第3式 单例模式 第4式 建造者模式 第5式 原型模式 结构型模式 第6式 适配器模式 第7式 桥接模式 第8式 组合模式 第9式 装饰器模式...
使用python实现葡萄酒威士忌风味特征分类
聚类威士忌 目的和描述:苏格兰威士忌因其复杂性和多样化的风味而备受推崇。据信,生产它的苏格兰地区具有独特的风味特征。在本案例研究中,我们将根据苏格兰威士忌的风味特征对其进行分类。我们将使用的数据集包含来自几个酿酒厂的精选苏格兰威士忌,我们将尝试将威士忌聚类…...
代理IP(代理服务器)的作用和注意事项
代理IP(也称代理服务器)是一种网络技术,可以用来隐藏用户的真实IP地址并代替其发起网络请求。这种技术在许多场景下都有广泛的应用,如加速网络访问、保护个人隐私、绕过地理限制等。下面将详细介绍代理IP的原理和应用。 原理 代理…...
问题解决 | Failed to initialize NVML: Driver/library version mismatch
问题描述: Ubuntu20.04服务器上,一个docker容器正在训练模型,打开另外一个docker容器时,出现以下错误 Error response from daemon: failed to create shim task: OCI runtime create failed: runc create failed: unable to st…...
ThinkPHP模型操作上
ThinkPHP模型操作上 前言模型一、创建模型二、模型操作 总结 前言 在mvc架构中,模型的解释是写逻辑代码的地方,其实还可以这样理解,就是一串操作写在一个模型类中,就是你要完成某一项功能,将这个功能的代码写在一个mod…...
053:cesium显示网格切片标识,展示X、Y、Level 坐标
第053个 点击查看专栏目录 本示例的目的是介绍如何在vue+cesium中加载瓦片网格切分标识地图。,它在切片方案中的每个渲染图块周围绘制一个框,并在其中绘制一个标签,指示图块的 X、Y、Level 坐标。 这主要用于调试地形和图像渲染问题。 直接复制下面的 vue+cesium源代码,操…...
FPGA基于XDMA实现PCIE X8视频采集HDMI输出 提供工程源码和QT上位机程序和技术支持
目录 1、前言2、我已有的PCIE方案3、PCIE理论4、总体设计思路和方案5、vivado工程详解6、驱动安装7、QT上位机软件8、上板调试验证9、福利:工程代码的获取 1、前言 PCIE(PCI Express)采用了目前业内流行的点对点串行连接,比起 PC…...
简单的redis master slave 配置
只做一个简单的master - slave 配置,新手试炼配置用。使用windows系统 master 配置 redis 默认,密码为空。首先配置redis(for master)的密码。 修改安装目录下的redis.windows.conf文件,搜索到requirepass, # requirepass foob…...
MySQL高级第十七篇:数据库主从复制原理及保证数据一致性
MySQL高级第十七篇:数据库主从复制原理及保证数据一致性 一、概述1. 提升数据库的并发能力2. 主从复制的作用? 二、主从复制原理三、搭建一主一从环境四、如何解决数据一致性问题?1. 方案一、异步复制2. 方案二、半同步复制3. 方案三、组复制…...
PM不想做项目管理了,还能干点啥?
做项目经理太累了! 那么 不做项目经理还能做什么呢? 01 铁锅批发商 毕竟 当项目经理的时候 已经囤积了成百上千口锅 十年背锅经验不是瞎吹 并且可现场演示铁锅烙饼 老板亲授,真实还原,充饥必备 02 Office优化师 当项目…...
Java面试被问Spring哑口无言?100道Spring面试考点解析
对于开发同学来说,Spring 框架熟悉又陌生。 熟悉:开发过程中无时无刻不在使用 Spring 的知识点;陌生:对于基本理论知识疏于整理与记忆。导致很多同学面试时对于 Spring 相关的题目知其答案,但表达不够完整准确。今天展…...
2023年制造业产品经理NPDP认证报名找弘博创新
产品经理国际资格认证NPDP是新产品开发方面的认证,集理论、方法与实践为一体的全方位的知识体系,为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会(PDMA)成立于1979年,是…...
Linux基础命令和基础知识总结
1. 常用文件管理命令介绍 (1) ctrl c: 取消命令,并且换行 (2) ctrl u: 清空本行命令 (3) tab键:可以补全命令和文件名,如果补全不了快速按两下tab键,可以显示备选选项 (4) ls: 列出当前目录下所有文件,蓝色的是文件夹&…...
Vue组件-非单文本组件
非单文本组件(用的少) 在vue中,组件是有两种编写格式的,第一种格式叫非单文本组件,第二种格式叫单文本组件 非单文本组件:一个文件中含有多个组件,也叫多文本组件,比如demo.html里面包含js,css… 单文本…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
反向工程与模型迁移:打造未来商品详情API的可持续创新体系
在电商行业蓬勃发展的当下,商品详情API作为连接电商平台与开发者、商家及用户的关键纽带,其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息(如名称、价格、库存等)的获取与展示,已难以满足市场对个性化、智能…...
Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...
算法:模拟
1.替换所有的问号 1576. 替换所有的问号 - 力扣(LeetCode) 遍历字符串:通过外层循环逐一检查每个字符。遇到 ? 时处理: 内层循环遍历小写字母(a 到 z)。对每个字母检查是否满足: 与…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
DeepSeek源码深度解析 × 华为仓颉语言编程精粹——从MoE架构到全场景开发生态
前言 在人工智能技术飞速发展的今天,深度学习与大模型技术已成为推动行业变革的核心驱动力,而高效、灵活的开发工具与编程语言则为技术创新提供了重要支撑。本书以两大前沿技术领域为核心,系统性地呈现了两部深度技术著作的精华:…...
