当前位置: 首页 > 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&…...

Vim 调用外部命令学习笔记

Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

应用升级/灾备测试时使用guarantee 闪回点迅速回退

1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间&#xff0c; 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点&#xff0c;不需要开启数据库闪回。…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

循环冗余码校验CRC码 算法步骤+详细实例计算

通信过程&#xff1a;&#xff08;白话解释&#xff09; 我们将原始待发送的消息称为 M M M&#xff0c;依据发送接收消息双方约定的生成多项式 G ( x ) G(x) G(x)&#xff08;意思就是 G &#xff08; x ) G&#xff08;x) G&#xff08;x) 是已知的&#xff09;&#xff0…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

uniapp微信小程序视频实时流+pc端预览方案

方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度​WebSocket图片帧​定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐​RTMP推流​TRTC/即构SDK推流❌ 付费方案 &#xff08;部分有免费额度&#x…...