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

区间覆盖 线段覆盖 二分

4195. 线段覆盖 - AcWing题库

P2082 区间覆盖(加强版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

做法:

void solve() {int n; cin>>n;vector<array<LL,2>> seg(n);for(auto &t: seg) cin>>t[0]>>t[1];sort(all(seg), [](array<LL,2> pre, array<LL,2> suf) {if(pre[0] == suf[0]) return pre[1] < suf[1];return pre[0] < suf[0];});vector<array<LL,2>> last;last.push_back(seg[0]);for(int i = 1; i < n; ++i) {if(seg[i][0] <= last.back()[1]) last.back()[1] = max(last.back()[1], seg[i][1]);else last.push_back(seg[i]);}LL ans = 0;for(auto &t: last) ans += t[1] - t[0] + 1;cout<<ans;
}

差分解决区间覆盖:(这题不能过,但是感觉这个做法有用)

void solve() {int n; cin>>n;vector<int> dif(1000 + 1);int rl = 0;rep(i,1,n) {int l, r; cin>>l>>r;dif[l]++;dif[r+1]--; rl = max(rl, r); }int sum = 0;int now = 0;rep(i,1,rl) {now += dif[i];if(now > 0) sum++;}cout<<sum;
}

4195. 线段覆盖 - AcWing题库

问题描述: 坐标轴中共有多少个整数坐标的点满足恰好被 k条线段覆盖。

思路:离散化差分,用map(。根据差分可以找线段被多少哥线段覆盖。

代码:

void solve() {int n; cin>>n;map<LL,LL> mll;vector<LL> ans(n + 1);rep(i,1,n) {LL l,r; cin>>l>>r;mll[l]++;mll[r+1]--;}LL last = -1,sum = 0;for(auto t: mll) {LL f = t.vf, s = t.vs;if(last != -1) ans[sum] += f - last;sum += s;last = f;}rep(i,1,n) cout<<ans[i]<<" ";
}

二分 (nowcoder.com)

问题描述:根据对话,找可能的最多正确的对话。

思路:

​ 如果是 val +,说明猜的数val比答案要大,此时,答案在区间(-inf, val)

​ 如果是val -,说明猜的数val比答案要小,此时,答案在区间(val, inf)

​ 如果是val .,说明猜的数val等于答案,此时,答案在区间[val, val + 1)

​ 可以用差分求最大覆盖区间。数据离散,可以用map代替差分离散化。

代码:

void solve() {LL inf = LONG_LONG_MAX - 123456789;int n; cin>>n;map<LL,LL> mll;char op[2];rep(i,1,n) {int v; cin>>v>>op;if(op[0] == '.') { // 等于 [val, val + 1)mll[v]++, mll[v+1]--;}else if(op[0] == '+') { // 大 (-inf, v)mll[-inf]++;mll[v]--; } else { // 小 (v+1, inf)mll[v+1]++;mll[inf]--;}}int ans = 0, sum = 0;for(auto t: mll) {sum += t.vs;ans = max(sum, ans);}cout<<ans;
}

【2023陕西训练营】day1 枚举和枚举优化 - Virtual Judge (vjudge.net)

相关文章:

区间覆盖 线段覆盖 二分

4195. 线段覆盖 - AcWing题库 P2082 区间覆盖&#xff08;加强版&#xff09; - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 做法&#xff1a; void solve() {int n; cin>>n;vector<array<LL,2>> seg(n);for(auto &t: seg) cin>>t[0]>>…...

F#奇妙游(20):主动模式

F#中主动模式的三种形式 F#中有一种特殊的模式匹配&#xff0c;叫做主动模式&#xff08;Active Pattern&#xff09;。主动模式可以让我们自定义模式匹配的方式&#xff0c;这样可以让我们的代码更加简洁&#xff0c;更加清晰。主动模式有三种形式&#xff0c;分别是&#xf…...

OLED透明屏与传统显示屏的区别:探索未来视觉体验的新里程碑

OLED透明屏作为一种新兴的显示技术&#xff0c;与传统显示屏相比&#xff0c;具有许多独特的特点和优势。 那么&#xff0c;在这篇文章中&#xff0c;尼伽便通过比较OLED透明屏和传统显示屏的区别&#xff0c;包括透明性、对比度、色彩表现力、节能环保等方面&#xff0c;为读…...

打开软件提示mfc100u.dll缺失是什么意思?要怎么处理?

当你打开某个软件或者运行游戏&#xff0c;系统提示mfc100u.dll丢失&#xff0c;此时这个软件或者游戏根本无法运行。其实&#xff0c;mfc100u.dll是动态库文件&#xff0c;它是VS2010编译的软件所产生的&#xff0c;如果电脑运行程序时提示缺少mfc100u.dll文件&#xff0c;程序…...

Python 基础 -- Tutorial(二)

5、数据结构 本章更详细地描述了一些你已经学过的东西&#xff0c;并添加了一些新的东西。 5.1. 更多关于Lists 列表(list)数据类型有更多的方法。下面是列表对象的所有方法: list.append(x) 在列表末尾添加一项。相当于a[len(a):] [x]。 list.extend(iterable) 通过添加可…...

11 迭代器|生成器|协程

文章目录 迭代器可迭代对象可迭代对象的本质iter()函数与 next()函数迭代器 Iterator样例 for...in...循环的本质使用的场景--斐波那契数列list和tuple也可以接收可迭代对象 生成器简介创建生成器方法一方法二总结 使用 send 唤醒 协程协程和线程差异简单实现协程greenletgeven…...

“第三方支付”详解!

第三方支付是什么&#xff1f;第三方支付的解释 中央银行官方解释&#xff1a;是与产品所在国和主要外资银行签订合同、具有一定实力和信誉保障的第三方独立机构提供的交易支持平台。在通过第三方支付平台进行的交易中&#xff0c;买方购买货物后&#xff0c;买方使用第三方平台…...

Rust之泛型、trait与生命周期

泛型是具体类型或其他属性的抽象替代。在编写代码时&#xff0c;可以直接描述泛型的行为&#xff0c;或者它与其他泛型产生的联系&#xff0c;而无须知晓它在编译和运行代码时采用的具体类型。 1、泛型数据类型&#xff1a; 们可以在声明函数签名或结构体等元素时使用泛型&am…...

GPU Microarch 学习笔记 [1]

WARP GPU的线程从thread grid 到thread block&#xff0c;一个thread block在CUDA Core上执行时&#xff0c;会分成warp执行&#xff0c;warp的颗粒度是32个线程。比如一个thread block可能有1024个线程&#xff0c;分成32个warp执行。 上图的CTA&#xff08;cooperative thre…...

Transformer(一)简述(注意力机制,NLP,CV通用模型)

目录 1.Encoder 1.1简单理解Attention 1.2.什么是self-attention 1.3.怎么计算self-attention 1.4.multi-headed&#xff08;q&#xff0c;k&#xff0c;v不区分大小写&#xff09; 1.5.位置信息表达 2.Decoder&#xff08;待补充&#xff09; 3.BERT 参考文献 1.Encode…...

回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测

回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测 目录 回归预测 | MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测预测效果基本介绍程序设计往期精彩参考资料 预测效果 基本介绍 MATLAB实现BiLSTM双向长短期记忆神经网络多输入多输出预测&#x…...

使用Dockker创建vwas容器时报错的解决方法

执行命令 docker run -it -d -p 13443:3443 --cap-add LINUX_IMMUTABLE secfa/docker-awvs没有详细看报错之前找了各种各样的解决办法&#xff0c;都无法解决。因此以后在看报错提示的时候耐心一点看关键词Error 后来才发现启动vwas时docker报了这个错&#xff1a; OSError: …...

【数据结构OJ题】链表分割

原题链接&#xff1a;https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70?tpId8&&tqId11004&rp2&ru/activity/oj&qru/ta/cracking-the-coding-interview/question-ranking 目录 1. 题目描述 2. 思路分析 3. 代码实现 1. 题目描述 2…...

无感知发布

什么是无感知发布 "无感知发布"是指在软件系统或应用程序进行更新或升级时&#xff0c;尽可能地避免对用户或系统的正常运行产生影响或中断。这种发布方式通常采用一系列技术和策略&#xff0c;以确保新版本的软件可以平滑地替代旧版本&#xff0c;而不会造成用户的…...

C++ 虚继承

C棱形继承 在 C 中&#xff0c;在使用 多继承 时&#xff0c;如果发生了如果类 A 派生出类 B 和类 C&#xff0c;类 D 继承自类 B 和类 C&#xff0c;这时候就发生了菱形继承。 如果发生了菱形继承&#xff0c;这个时候类 A 中的 成员变量 和 成员函数 继承到类 D 中变成了两…...

git commit用法

git commit 是 Git 版本控制系统中的一个命令&#xff0c;用于将更改提交到本地存储库。以下是 git commit 的一些常见用法和选项&#xff1a; 基本用法: git commit -m "提交信息"使用 -m 选项可以直接在命令行中添加提交信息。 提交所有更改: git commit -a -m &q…...

【LeetCode】543.二叉树的直径

题目 给你一棵二叉树的根节点&#xff0c;返回该树的 直径 。 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。 两节点之间路径的 长度 由它们之间边数表示。 示例 1&#xff1a; 输入&#xff1a;root [1,2,3,4,5]…...

TypeScript教程(五)条件语句,循环,函数

一、条件语句 条件语句基于不同的条件来执行不同的动作 1.if语句&#xff1a;只有当指定条件为true时&#xff0c;使用该语句来执行代码 2.if...else语句&#xff1a;当条件为true时执行代码&#xff0c;当条件为else时执行其他代码 3.if...else if...else语句&#xff1a;…...

vue使用jsplumb 流程图

安装jsPlumb库&#xff1a;在Vue项目中使用npm或yarn安装jsPlumb库。 npm install jsplumb 创建一个Vue组件&#xff1a;创建一个Vue组件来容纳jsPlumb的功能和呈现。 <template><div style"margin: 20px"><div style"margin: 20px">&l…...

【BASH】回顾与知识点梳理(二十八)

【BASH】回顾与知识点梳理 二十八 二十八. 例行性工作排程(crontab)28.1 什么是例行性工作排程Linux 工作排程的种类&#xff1a; at, cronCentOS Linux 系统上常见的例行性工作 28.2 仅执行一次的工作排程atd 的启动at 的运作方式实际运作单一工作排程at 工作的管理batch&…...

【网络】每天掌握一个Linux命令 - iftop

在Linux系统中&#xff0c;iftop是网络管理的得力助手&#xff0c;能实时监控网络流量、连接情况等&#xff0c;帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...

SkyWalking 10.2.0 SWCK 配置过程

SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外&#xff0c;K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案&#xff0c;全安装在K8S群集中。 具体可参…...

线程同步:确保多线程程序的安全与高效!

全文目录&#xff1a; 开篇语前序前言第一部分&#xff1a;线程同步的概念与问题1.1 线程同步的概念1.2 线程同步的问题1.3 线程同步的解决方案 第二部分&#xff1a;synchronized关键字的使用2.1 使用 synchronized修饰方法2.2 使用 synchronized修饰代码块 第三部分&#xff…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...