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

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 题目描述 省选终于考完了&#xff0c;但是还是不出成绩&#xff0c;Fancy 非常焦急而忧伤的等待着。 闲着无聊的 Fancy 打开书包拿出了一张纸和一支笔&#xff0c;在纸上画了一行n个…...

06 【Sass语法介绍-函数】

这篇文章只更新了颜色函数&#xff0c;由于Sass使用时间过短&#xff0c;其它函数参考官网 1.前言 Sass 中的函数&#xff0c;这在 Sass 中是比较强大的一个功能&#xff0c;同时使用场景和语法也比较多&#xff0c;所以本节内容篇幅较长&#xff0c;但你一定要好好学习&#…...

入参校验产品化 schema

与规则引擎不同,规则面向技术, 传入data, 返回 所有异常字段和原因. 面向技术, 先有对象,再有规则, 如何通过交互来编写schema是个难题? 和json-schema区别: 思路上就是反过来的, 面相产品, schema可视化编辑器, 是面向结构设计. 现有模型,才有数据, 才可以编程. 基于配置…...

【Linux】7、一篇文章学习 Linux 中一些硬核的常用知识

目录 一、systemctl二、软链接三、日期&#xff08;date 命令&#xff09;四、Linux 的时区(1) 修改时区(2) ntp 五、IP 地址六、主机名七、域名解析八、配置 Linux 的固定 IP 地址(1) 在 VMwareWorkstation 中配置 IP 地址网关和网段&#xff08;IP 地址的范围&#xff09;(2)…...

gpt4-如何使用

gpt-4怎么用 目前&#xff0c;GPT-4尚未发布或公开释放。因此&#xff0c;我们目前无法使用GPT-4。GPT-4是由OpenAI公司开发的人工智能语言模型&#xff0c;其预计能够比先前的版本GPT-3更加强大和智能化&#xff0c;但我们需要等待OpenAI官方发布有关GPT-4的更多信息。 如果您…...

定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现?

定时每天凌晨一点在linux系统上执行一个autobuild.sh脚本如何实现&#xff1f; 可以使用linux的计划任务功能crontab来实现定时执行脚本。 具体步骤如下: 编辑crontab计划任务列表: bash crontab -e 这会打开一个文本编辑器,你可以在里面添加计划任务。添加一行计划任务,内容如…...

C++ 设计模式23:访问者模式

C++ 23种设计模式系列文章目录 创建型模式 第1式 工厂方法模式 第2式 抽象工厂模式 第3式 单例模式 第4式 建造者模式 第5式 原型模式 结构型模式 第6式 适配器模式 第7式 桥接模式 第8式 组合模式 第9式 装饰器模式...

使用python实现葡萄酒威士忌风味特征分类

聚类威士忌 目的和描述:苏格兰威士忌因其复杂性和多样化的风味而备受推崇。据信,生产它的苏格兰地区具有独特的风味特征。在本案例研究中,我们将根据苏格兰威士忌的风味特征对其进行分类。我们将使用的数据集包含来自几个酿酒厂的精选苏格兰威士忌,我们将尝试将威士忌聚类…...

代理IP(代理服务器)的作用和注意事项

代理IP&#xff08;也称代理服务器&#xff09;是一种网络技术&#xff0c;可以用来隐藏用户的真实IP地址并代替其发起网络请求。这种技术在许多场景下都有广泛的应用&#xff0c;如加速网络访问、保护个人隐私、绕过地理限制等。下面将详细介绍代理IP的原理和应用。 原理 代理…...

问题解决 | Failed to initialize NVML: Driver/library version mismatch

问题描述&#xff1a; Ubuntu20.04服务器上&#xff0c;一个docker容器正在训练模型&#xff0c;打开另外一个docker容器时&#xff0c;出现以下错误 Error response from daemon: failed to create shim task: OCI runtime create failed: runc create failed: unable to st…...

ThinkPHP模型操作上

ThinkPHP模型操作上 前言模型一、创建模型二、模型操作 总结 前言 在mvc架构中&#xff0c;模型的解释是写逻辑代码的地方&#xff0c;其实还可以这样理解&#xff0c;就是一串操作写在一个模型类中&#xff0c;就是你要完成某一项功能&#xff0c;将这个功能的代码写在一个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、福利&#xff1a;工程代码的获取 1、前言 PCIE&#xff08;PCI Express&#xff09;采用了目前业内流行的点对点串行连接&#xff0c;比起 PC…...

简单的redis master slave 配置

只做一个简单的master - slave 配置&#xff0c;新手试炼配置用。使用windows系统 master 配置 redis 默认&#xff0c;密码为空。首先配置redis(for master)的密码。 修改安装目录下的redis.windows.conf文件&#xff0c;搜索到requirepass&#xff0c; # requirepass foob…...

MySQL高级第十七篇:数据库主从复制原理及保证数据一致性

MySQL高级第十七篇&#xff1a;数据库主从复制原理及保证数据一致性 一、概述1. 提升数据库的并发能力2. 主从复制的作用&#xff1f; 二、主从复制原理三、搭建一主一从环境四、如何解决数据一致性问题&#xff1f;1. 方案一、异步复制2. 方案二、半同步复制3. 方案三、组复制…...

PM不想做项目管理了,还能干点啥?

做项目经理太累了&#xff01; 那么 不做项目经理还能做什么呢&#xff1f; 01 铁锅批发商 毕竟 当项目经理的时候 已经囤积了成百上千口锅 十年背锅经验不是瞎吹 并且可现场演示铁锅烙饼 老板亲授&#xff0c;真实还原&#xff0c;充饥必备 02 Office优化师 当项目…...

Java面试被问Spring哑口无言?100道Spring面试考点解析

对于开发同学来说&#xff0c;Spring 框架熟悉又陌生。 熟悉&#xff1a;开发过程中无时无刻不在使用 Spring 的知识点&#xff1b;陌生&#xff1a;对于基本理论知识疏于整理与记忆。导致很多同学面试时对于 Spring 相关的题目知其答案&#xff0c;但表达不够完整准确。今天展…...

2023年制造业产品经理NPDP认证报名找弘博创新

产品经理国际资格认证NPDP是新产品开发方面的认证&#xff0c;集理论、方法与实践为一体的全方位的知识体系&#xff0c;为公司组织层级进行规划、决策、执行提供良好的方法体系支撑。 【认证机构】 产品开发与管理协会&#xff08;PDMA&#xff09;成立于1979年&#xff0c;是…...

Linux基础命令和基础知识总结

1. 常用文件管理命令介绍 (1) ctrl c: 取消命令&#xff0c;并且换行 (2) ctrl u: 清空本行命令 (3) tab键&#xff1a;可以补全命令和文件名&#xff0c;如果补全不了快速按两下tab键&#xff0c;可以显示备选选项 (4) ls: 列出当前目录下所有文件&#xff0c;蓝色的是文件夹&…...

Vue组件-非单文本组件

非单文本组件(用的少) 在vue中&#xff0c;组件是有两种编写格式的&#xff0c;第一种格式叫非单文本组件&#xff0c;第二种格式叫单文本组件 非单文本组件&#xff1a;一个文件中含有多个组件&#xff0c;也叫多文本组件&#xff0c;比如demo.html里面包含js,css… 单文本…...

深度学习在微纳光子学中的应用

深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向&#xff1a; 逆向设计 通过神经网络快速预测微纳结构的光学响应&#xff0c;替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

IT供电系统绝缘监测及故障定位解决方案

随着新能源的快速发展&#xff0c;光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域&#xff0c;IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选&#xff0c;但在长期运行中&#xff0c;例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

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

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

Rust 开发环境搭建

环境搭建 1、开发工具RustRover 或者vs code 2、Cygwin64 安装 https://cygwin.com/install.html 在工具终端执行&#xff1a; rustup toolchain install stable-x86_64-pc-windows-gnu rustup default stable-x86_64-pc-windows-gnu ​ 2、Hello World fn main() { println…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...