市长海报/ Mayor‘s posters

AB 省 Bytetown 的市民无法忍受市长竞选活动的候选人随心所欲地将他们的选举海报贴在各个地方。市议会最终决定建造一面选举墙来放置海报,并引入以下规则:
  • 每个候选人都可以在墙上放置一张海报。
  • 所有海报的高度都与墙壁的高度相同;海报的宽度可以是任意整数字节(byte 是 Bytetown 中的长度单位)。
  • 墙被分成几段,每段的宽度为 1 个字节。
  • 每张海报必须完全覆盖连续数量的墙段。

他们建造了一堵 10000000 字节长的墙(这样就有足够的空间容纳所有候选人)。当竞选活动重新开始时,候选人将他们的海报贴在墙上,他们的海报宽度差异很大。此外,候选人开始将他们的海报张贴在已经被其他海报占据的墙面上。Bytetown 的每个人都很好奇,在选举前的最后一天,谁的海报将(全部或部分)可见。
您的任务是根据海报的大小、位置和在选举墙上的放置顺序等信息,找出放置所有海报时可见海报的数量。

输入

输入的第一行包含一个数字 c,给出后面的 case 数。单个案例的第一行数据包含数字 1 <= n <= 10000。随后的 n 行按海报的放置顺序描述海报。n 行中的第 i 行包含两个整数 li 和 ri,分别是第 i 张海报的左端和右端所占据的墙段编号。我们知道,对于每个 1 <= i <= n, 1 <= li <= ri <= 10000000。放置第 i 张海报后,它将完全覆盖编号为 li、li+1 ,... , ri 的所有墙段。

输出

对于每个输入数据集,在放置所有海报后打印可见海报的数量。

下图说明了 sample input 的情况。

样本

输入复制输出复制
1
5
1 4
2 6
8 10
3 4
7 10
4

思路:

 因为范围比较大,所以用离散化将其范围变小,然后在用线段树做题

代码:

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct sss {int x, y, k;
}a[80005];//线段树
bool b[10005];//判断海报是否访问过
struct ss {int x, i;//i 第i个坐标bool v;//判断是左边还是右边边界
}c[20005],e[20005];//归并离散化,减少范围
struct s{int	x, y;
}d[10005];//离散化后的墙段
int f, n, x, y;
//建立线段树
void bulid(int i,int x, int y) {a[i].x = x;a[i].y = y;a[i].k = 0;if (x == y) {return;}int mid = (x + y) / 2;bulid(2 * i, x, mid);bulid(2 * i + 1, mid + 1, y);
}
//线段树的区间修改
void tianjia(int i, int x, int y, int j) {if (a[i].x >= x && a[i].y <= y) {a[i].k = j;return;}else if((a[i].x < x && a[i].y >=x)||(a[i].x <=y && a[i].y > y)){if (a[i].x == a[i].y) {return;}if (a[i].k != 0) {a[i * 2 + 1].k = a[i].k;a[i * 2].k = a[i].k;a[i].k = 0;}int mid = (a[i].x + a[i].y) / 2;if (mid >= x)tianjia(2 * i, x, y, j);if (mid < y)tianjia(2 * i + 1, x, y, j);}else {return;}
}
//清除痕迹
void qingchu(int i) {a[i].k = 0;if(a[i].x!=a[i].y){qingchu(i * 2);qingchu(i * 2 + 1);}
}
//查询多少海报漏出来
void chazhao(int i,int &q) {if (a[i].k != 0) {if(b[a[i].k] == false){q++;b[a[i].k] = true;			}qingchu( i);return;}else if (a[i].x == a[i].y) {return;}else {chazhao(i * 2, q);chazhao(i * 2 + 1, q);}
}
//归并排序
void guibing(int i, int j) {if (i >= j) {return;}int mid = i + (j - i) / 2;guibing(i, mid);guibing(mid + 1, j);int r = i, l = mid + 1, h = i;while (r <= mid && l <= j) {if (c[r].x < c[l].x) {e[h] = c[r];h++;r++;}else {e[h] = c[l];h++;l++;}}while (r <= mid) {e[h]= c[r];h++;r++;}while (l <= j) {e[h] = c[l];h++;l++;}h = i;while (h <= j) {c[h] = e[h];h++;}}
int main(){scanf("%d", &f);bulid(1, 1, 20000);while (f--) {scanf("%d", &n);for(int i=1;i<=n;i++){scanf("%d %d", &c[i].x, &c[n+i].x);c[i].i = i, c[i].v = true;c[i + n].i = i; c[i+n].v = false;}//记录,方便后序离散化guibing(1, 2 * n);int j = 1;for (int i = 1; i <= 2 * n; i++) {if (c[i].x != c[j].x)j=i;//使相同的数离散化后相同if (c[i].v == true)d[c[i].i].x = j;elsed[c[i].i].y = j;}//区间修改for (int i = 1; i <= n; i++) {tianjia(1, d[i].x, d[i].y, i);}//查找记录int q = 0;chazhao(1, q);printf("%d\n", q);//清除标记memset(b, false, (n+1)*sizeof(bool));}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35145.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LeetCode hot 100—验证二叉搜索树

题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 示例 1&#…

ccfcsp3402矩阵重塑(其二)

//矩阵重塑&#xff08;其二&#xff09; #include<iostream> using namespace std; int main(){int n,m,t;cin>>n>>m>>t;int c[10000][10000];int s0,sum0;int d[10000],k[100000];for(int i0;i<n;i){for(int j0;j<m;j){cin>>c[i][j];d[s…

MCP和Function Calling的区别

文章目录 1、什么是MCP1.1、定义和特点1.2、架构和工作原理3.3、MCP 的主要优势 2、什么是Function Calling3、MCP和Function Calling的区别4、总结 &#x1f343;作者介绍&#xff1a;双非本科大四网络工程专业在读&#xff0c;阿里云专家博主&#xff0c;前三年专注于Java领域…

裂缝识别系统 Matlab GUI设计

使用说明 裂缝识别系统 Matlab GUI设计 &#xff0c;运行环境Matlab2023b及以上&#xff1b; 一种基于MATLAB图形用户界面&#xff08;GUI&#xff09;的裂缝自动识别系统&#xff0c;该系统利用数字图像处理技术实现裂缝图像的预处理&#xff0c;集成均衡化、噪声滤波、对比…

【源码分析】Nacos实例注册流程分析-事件驱动框架

【踩坑记录】 本人下载的Nacos 服务端版本是2.3.2&#xff0c;在开始进行源码编译便遇到问题&#xff0c;下面是各个问题记录 源码大量爆红 在最开始用Idea加载Maven项目的时候&#xff0c;发现项目中大量的代码爆红&#xff0c;提示其类或者包不存在&#xff0c;后来结果查…

51单片机指令系统入门

目录 基本概念讲解 一、机器指令​ 二、汇编指令​ &#xff08;一&#xff09;汇编指令的一般格式 &#xff08;二&#xff09;按字节数分类的指令 三、高级指令 总结​ 基本概念讲解 指令是计算机&#xff08;或单片机&#xff09;中 CPU 能够识别并执行的基本操作命令…

mysql5.x和mysql8.x查看和设置隔离级别

MySQL的隔离级别 级别标志值描述读未提交READ-UNCOMMITTED0存在脏读、不可重复读、幻读的问题读已提交READ-COMMITTED1解决脏读的问题&#xff0c;存在不可重复读、幻读的问题可重复读REPEATABLE-READ2mysql 默认级别&#xff0c;解决脏读、不可重复读的问题&#xff0c;存在幻…

【函数式编程】【C#/F#】第四讲:单子与函子 - 抽象的编程模式

在第二讲中我们探讨了一个诚实的函数应该要做到什么事&#xff0c;并运用了一种方法&#xff0c;让我们可以去准确的描述数据。 不过有一种情况让我们始料未及&#xff0c;例如网站需要收集一些信息&#xff0c;但有些信息不是必须的&#xff0c;是可有可无的。如果我们要去准…

【vue2 + Cesium】使用Cesium、添加第三方地图、去掉商标、Cesium基础配置、地图放大缩小事件、获取可视区域、层级、高度

参考文章&#xff1a; vue2 使用 cesium 篇【第一篇】 vue2 使用 cesium 【第二篇-相机视角移动添加模型】 vue2 项目模版&#xff1a; vue2-common 安装 cesium npm install cesium --save这个就很简单&#xff0c;只需要一句简简单单的命令就可以实现在 vue 项目中安装 ce…

vllm-openai多服务器集群部署AI模型

服务器配置是两台ubantu系统电脑,每台电脑安装两张4090-48G显存的显卡,共计192G显存。 服务器1 服务器2 准备工作: 1.两台电脑都已经安装了docker 2.两台电脑都已经安装了nvidia驱动 参考vllm官方资料 https://docs.vllm.ai/en/latest/serving/distributed_serving.html…

【电源】斩波电路

文章目录 前言定义概念 缩写降压斩波电路使用步骤总结参考文献 前言 进行大创项目开发的学习 bilibili 定义概念 缩写 斩波电路&#xff1a;分为降压&#xff0c;电荷泵&#xff0c;升压&#xff0c;升降压&#xff0c;Cuk&#xff0c;Speic&#xff0c;Zeta 等等 降压斩…

Hadoop集群组成

&#xff08;一&#xff09;Hadoop的组成 对普通用户来说&#xff0c; Hadoop就是一个东西&#xff0c;一个整体&#xff0c;它能给我们提供无限的磁盘用来保存文件&#xff0c;可以使用提供强大的计算能力。 在Hadoop3.X中&#xff0c;hadoop一共有三个组成部…

c++基础知识-图论进阶

一、拓扑排序 1、基础知识 1&#xff09;什么是拓扑排序 对一个有向无环图G进行拓扑排序&#xff0c;是将G中所有顶点排成一个线性序列&#xff0c;使得图中任意一对顶点u和v&#xff0c;若&#xff0c;则u在线性序列中出现在v之前。 2&#xff09;拓扑排序的操作方法 重复执行…

从Scaling Laws中解析大模型训练的边际递减临界点

前言 当我们拆解GPT-4到DeepSeek的演进路径&#xff0c;会发现一个反直觉的真相&#xff1a;​AI的智能跃迁不依赖参数堆砌&#xff0c;而取决于对"结构-能量-信息"三元关系的精准把控。就像人类大脑在进化中通过皮层折叠而非单纯增大体积来实现智能突破&#xff0c…

Word 小黑第20套

对应大猫21 特定一页设为横向 上下用分页符

【从0到1搞懂大模型】RNN基础(4)

先说几个常用的可以下载数据集的地方 平台&#xff1a;kaggle&#xff08;https://www.kaggle.com/datasets&#xff09; 和鲸社区&#xff08;https://www.heywhale.com/home&#xff09; 阿里天池&#xff08;https://tianchi.aliyun.com/&#xff09; 其他&#xff1a;海量公…

openEuler24.03 LTS下安装MySQL8

前提条件 拥有openEuler24.03 LTS环境&#xff0c;可参考&#xff1a;Vmware下安装openEuler24.03 LTS 步骤 卸载原有mysql及mariadb sudo systemctl stop mysql mysqld 2>/dev/null sudo rpm -qa | grep -i mysql\|mariadb | xargs -n1 sudo rpm -e --nodeps 2>/dev/…

如何在Odoo 18中实现OWL通知服务

如何在Odoo 18中实现OWL通知服务 OWL&#xff08;Odoo Web Library&#xff09;是Odoo的前端框架&#xff0c;用于构建现代化的动态响应式用户界面。在早期版本中&#xff0c;Odoo 前端设计与开发使用的是诸如 QWeb 这类较为老旧的框架&#xff0c;而随着 Odoo 每发布一个新版本…

Unet nn-Unet

Unet && nn-Unet&#xff1a; 文章题目&#xff1a;U-Net: Convolutional Networks for Biomedical Image Segmentation 代码&#xff1a;https://lmb.informatik.uni-freiburg.de/people/ronneber/u-net/ 文章题目&#xff1a;nnU-Net: Self-adapting Framework for U…

【扩散模型入门】Latent Diffusion

1. 概述 扩散模型为公众所知的一个主要原因是Stable Diffusion(SD)的推出展现出了远超以往的图像合成效果,而SD的主要技术就是Latent Diffusion Model(LDM)。 实际上,LDM的核心idea非常简单: 为了确保生成质量,LDM尽可能提升去噪模型的规模。提升模型规模往往也会同步…