2023NOIP A层联测9-天竺葵
天竺葵/无法阻挡的子序列/很有味道的题目
我们称一个长度为 k k k 的序列 c c c 是好的,当且仅当对任意正整数 i i i 在 [ 1 , k − 1 ] [1,k-1] [1,k−1] 中,满足 c i + 1 > b i × c i c_{i+1}>b_i \times c_i ci+1>bi×ci, b b b 序列在下文描述。
小 L 现在给你两个序列 a , b a,b a,b,你需要从 a a a 序列中找出一个最长的子序列 c c c,使得 c c c 是好的。
输出这个最长的子序列的长度即可。
暂且把这个问题叫做带权最长上升子序列。
显然,类似于求 L I S LIS LIS,如果我们在 a a a 序列的前 i i i 个数中已经选了一个好的序列 c c c,那么 c c c 的最后一个一定是最小的(因为后面更容易满足条件增加长度)。
于是用二分, l o w i low_i lowi 表示长度为 i i i 的带权最长上升子序列的 a i ⋅ b i a_i\cdot b_i ai⋅bi 的最小值。
每次用 lower_bound \texttt{lower\_bound} lower_bound 在 l o w low low 中查找大于等于 a i a_i ai 的第一个位置,用 a i ⋅ b i a_i\cdot b_i ai⋅bi 更新该位置,同时记录答案。
这样就做完了。
细节详见代码。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ans=1;
ll a[1000001],b[1000001],low[1000001];
ll read()
{ll sum=0;int c=getchar();while(c<48||c>57) c=getchar();while(c>=48&&c<=57) sum=sum*10+c-48,c=getchar();return sum;
}
int main()
{freopen("C.in","r",stdin);freopen("C.out","w",stdout);n=read();for(int i=1;i<=n;i++) a[i]=read();for(int i=1;i<=n;i++) b[i]=read();memset(low,0x3f,sizeof(low));for(int i=1;i<=n;i++){int czn=lower_bound(low+1,low+1+ans,a[i])-low;ans=max(ans,czn);low[czn]=min(a[i]*b[czn],low[czn]);}cout<<ans;
}
相关文章:
2023NOIP A层联测9-天竺葵
天竺葵/无法阻挡的子序列/很有味道的题目 我们称一个长度为 k k k 的序列 c c c 是好的,当且仅当对任意正整数 i i i 在 [ 1 , k − 1 ] [1,k-1] [1,k−1] 中,满足 c i 1 > b i c i c_{i1}>b_i \times c_i ci1>bici, …...
react antd table表格点击一行选中数据的方法
一、前言 antd的table,默认是点击左边的单选/复选按钮,才能选中一行数据; 现在想实现点击右边的部分,也可以触发操作选中这行数据。 可以使用onRow实现,样例如下。 二、代码 1.表格样式部分 //表格table样式部分{…...
【VUEX】最好用的传参方式--Vuex的详解
🥳🥳Welcome Huihuis Code World ! !🥳🥳 接下来看看由辉辉所写的关于VuexElementUI的相关操作吧 目录 🥳🥳Welcome Huihuis Code World ! !🥳🥳 一.Vuex是什么 1.定义 2…...
【.net core】yisha框架 SQL SERVER数据库 反向递归查询部门(子查父)
业务service.cs中ListFilter方法中内容 //反向递归查询部门列表List<DepartmentEntity> departmentList await departmentService.GetReverseRecurrenceList(new DepartmentListParam() { Ids operatorInfo.DepartmentId.ToString() });if (departmentList ! null &am…...
java处理时间-去除节假日以及双休日
文章目录 一、建表:activity_holiday_info二、java代码1、ActivitityHolidayController.java2、ActivityHolidayInfoService.java3、ActivityHolidayInfoServiceImpl.java 三、测试效果 有些场景需要计算数据非工作日的情况,eg:统计每个人每月工作日签到…...
快讯|Tubi 有 Rabbit AI 啦
在每月一期的 Tubi 快讯中,你将全面及时地获取 Tubi 最新发展动态,欢迎星标关注【比图科技】微信公众号,一起成长变强! Tubi 推出 Rabbit AI 帮助用户找到喜欢的视频内容 Tubi 于今年九月底推出了 Rabbit AI,这是一项…...
Zookeeper从入门到精通
Zookeeper 是一个开源的分布式协调服务,目前由 Apache 进行维护。Zookeeper 可以用于实现分布式系统中常见的发布/订阅、负载均衡、命令服务、分布式协调/通知、集群管理、Master 选举、分布式锁和分布式队列等功能。 目录 01-Zookeeper特性与节点数据类型详解02-Z…...
10.11作业
多继承代码实现沙发床 #include <iostream>using namespace std;class Sofa {private:int h;public:Sofa() {cout << "Sofa无参构造" << endl;}Sofa(int h): h(h) {cout << "Sofa有参构造" << endl;}Sofa(const Sofa& …...
如何对比github中不同commits的区别
有时候想要对比跨度几十个commits之前的代码区别,想直接使用github的用户界面。可以直接在官网操作。 示例 首先要创建一个旧commit的branch。进入该旧的commit,然后输入branch名字即可。 然后在项目网址后面加上compare即可对比旧的branch和新的bran…...
串的基本操作(数据结构)
串的基本操作 #include <stdlib.h> #include <iostream> #include <stdio.h> #define MaxSize 255typedef struct{char ch[MaxSize];int length; }SString;//初始化 SString InitStr(SString &S){S.length0;return S; } //为了方便计算,串的…...
ctfshow-web12(glob绕过)
打开链接,在网页源码里找到提示 要求以get请求方式给cmd传入参数 尝试直接调用系统命令,没有回显,可能被过滤了 测试phpinfo,回显成功,确实存在了代码执行 接下来我们尝试读取一下它存在的文件,这里主要介…...
hive3.1核心源码思路
系列文章目录 大数据主要组件核心源码解析 文章目录 系列文章目录大数据主要组件核心源码解析 前言一、HQL转化为MR 核心思路二、核心代码1. 入口类,生命线2. 编译代码3. 执行代码 总结 前言 提示:这里可以添加本文要记录的大概内容: 对大…...
LATR:3D Lane Detection from Monocular Images with Transformer
参考代码:LATR 动机与主要工作: 之前的3D车道线检测算法使用诸如IPM投影、3D anchor加NMS后处理等操作处理车道线检测,但这些操作或多或少会存在一些负面效应。IPM投影对深度估计和相机内外参数精度有要求,anchor的方式需要一些如…...
什么是UI自动化测试工具?
UI自动化测试工具有着AI技术驱动,零代码开启自动化测试,集设备管理与自动化能力于一身的组织级自动化测试管理平台。基于计算机视觉技术,可跨平台、跨载体执行脚本,脚本开发和维护效率提升至少50%;多端融合统一用户使用体验&#…...
计算顺序表中值在100到500之间的元素个数
要求顺序表中值在100到500之间的元素的个数,你可以使用C语言编写一个循环来遍历顺序表中的元素,并在循环中检查每个元素是否在指定的范围内。 #include <stdio.h>#define MAX_SIZE 100 // 假设顺序表的最大容量为100int main() {int arr[MAX_SIZE]…...
【问题总结】级数的括号可以拆吗?
问题 今天在做题的时候发现,括号这个问题时常出现。Σun,Σvn,和Σ(unvn),两个级数涉及到了括号增删,Σ(un-1un),级数钟的前后项的合并也涉及到了括号增删。 总结 添括号定理&…...
抖音自动养号脚本+抖音直播控场脚本
功能描述 一.抖音功能 1.垂直浏览 2.直播暖场 3.精准引流 4.粉丝留言 5.同城引流 6.取消关注 7.万能引流 8.精准截流 9.访客引流 10.直播间引流 11.视频分享 12.榜单引流 13.搜索引流 14.点赞回访 15.智能引流 16.关注回访 介绍下小红书数据挖掘 搜索关键词&…...
uvm中transaction的response和id的解读
在公司写代码的时候发现前辈有一段这样的代码: ....//其他transaction uvm_create(trans);........ uvm_send(trans); tmp_id trans.get_transaction_id(); get_response(rsp,tmp_id); 如果前面有其他transaction,这段代码里的get_response不带id的话…...
第四节(1):EXCEL中判断一个WORD文件是否被打开
《VBA信息获取与处理》教程(10178984)是我推出第六套教程,目前已经是第一版修订了。这套教程定位于最高级,是学完初级,中级后的教程。这部教程给大家讲解的内容有:跨应用程序信息获得、随机信息的利用、电子邮件的发送、VBA互联网…...
java.util.concurrent.locks.Condition详解
Condition翻译成中文是“条件”,一般我们称其为条件变量,每一个Condition对象都通过链表保存了一个队列,我们称之为条件队列。 当然了,这里所说的Condition对象一般指的是Condition接口的实现类ConditionObject,比如我…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
react菜单,动态绑定点击事件,菜单分离出去单独的js文件,Ant框架
1、菜单文件treeTop.js // 顶部菜单 import { AppstoreOutlined, SettingOutlined } from ant-design/icons; // 定义菜单项数据 const treeTop [{label: Docker管理,key: 1,icon: <AppstoreOutlined />,url:"/docker/index"},{label: 权限管理,key: 2,icon:…...
CSS 工具对比:UnoCSS vs Tailwind CSS,谁是你的菜?
在现代前端开发中,Utility-First (功能优先) CSS 框架已经成为主流。其中,Tailwind CSS 无疑是市场的领导者和标杆。然而,一个名为 UnoCSS 的新星正以其惊人的性能和极致的灵活性迅速崛起。 这篇文章将深入探讨这两款工具的核心理念、技术差…...
OpenGL-什么是软OpenGL/软渲染/软光栅?
软OpenGL(Software OpenGL)或者软渲染指完全通过CPU模拟实现的OpenGL渲染方式(包括几何处理、光栅化、着色等),不依赖GPU硬件加速。这种模式通常性能较低,但兼容性极强,常用于不支持硬件加速…...
