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… 单文本…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする
日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
select、poll、epoll 与 Reactor 模式
在高并发网络编程领域,高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表,以及基于它们实现的 Reactor 模式,为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。 一、I…...
安卓基础(aar)
重新设置java21的环境,临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的: MyApp/ ├── app/ …...
Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
并发编程 - go版
1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程,系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现企业微信功能
1. 开发环境准备 安装DevEco Studio 3.1: 从华为开发者官网下载最新版DevEco Studio安装HarmonyOS 5.0 SDK 项目配置: // module.json5 {"module": {"requestPermissions": [{"name": "ohos.permis…...
