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

2023NOIP A层联测9-天竺葵

天竺葵/无法阻挡的子序列/很有味道的题目

我们称一个长度为 k k k 的序列 c c c 是好的,当且仅当对任意正整数 i i i [ 1 , k − 1 ] [1,k-1] [1,k1] 中,满足 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 aibi 的最小值。

每次用 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 aibi 更新该位置,同时记录答案。

这样就做完了。

细节详见代码。

#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 是好的&#xff0c;当且仅当对任意正整数 i i i 在 [ 1 , k − 1 ] [1,k-1] [1,k−1] 中&#xff0c;满足 c i 1 > b i c i c_{i1}>b_i \times c_i ci1​>bi​ci​&#xff0c; …...

react antd table表格点击一行选中数据的方法

一、前言 antd的table&#xff0c;默认是点击左边的单选/复选按钮&#xff0c;才能选中一行数据&#xff1b; 现在想实现点击右边的部分&#xff0c;也可以触发操作选中这行数据。 可以使用onRow实现&#xff0c;样例如下。 二、代码 1.表格样式部分 //表格table样式部分{…...

【VUEX】最好用的传参方式--Vuex的详解

&#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 接下来看看由辉辉所写的关于VuexElementUI的相关操作吧 目录 &#x1f973;&#x1f973;Welcome Huihuis Code World ! !&#x1f973;&#x1f973; 一.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 三、测试效果 有些场景需要计算数据非工作日的情况&#xff0c;eg&#xff1a;统计每个人每月工作日签到…...

快讯|Tubi 有 Rabbit AI 啦

在每月一期的 Tubi 快讯中&#xff0c;你将全面及时地获取 Tubi 最新发展动态&#xff0c;欢迎星标关注【比图科技】微信公众号&#xff0c;一起成长变强&#xff01; Tubi 推出 Rabbit AI 帮助用户找到喜欢的视频内容 Tubi 于今年九月底推出了 Rabbit AI&#xff0c;这是一项…...

Zookeeper从入门到精通

Zookeeper 是一个开源的分布式协调服务&#xff0c;目前由 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之前的代码区别&#xff0c;想直接使用github的用户界面。可以直接在官网操作。 示例 首先要创建一个旧commit的branch。进入该旧的commit&#xff0c;然后输入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; } //为了方便计算&#xff0c;串的…...

ctfshow-web12(glob绕过)

打开链接&#xff0c;在网页源码里找到提示 要求以get请求方式给cmd传入参数 尝试直接调用系统命令&#xff0c;没有回显&#xff0c;可能被过滤了 测试phpinfo&#xff0c;回显成功&#xff0c;确实存在了代码执行 接下来我们尝试读取一下它存在的文件&#xff0c;这里主要介…...

hive3.1核心源码思路

系列文章目录 大数据主要组件核心源码解析 文章目录 系列文章目录大数据主要组件核心源码解析 前言一、HQL转化为MR 核心思路二、核心代码1. 入口类&#xff0c;生命线2. 编译代码3. 执行代码 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 对大…...

LATR:3D Lane Detection from Monocular Images with Transformer

参考代码&#xff1a;LATR 动机与主要工作&#xff1a; 之前的3D车道线检测算法使用诸如IPM投影、3D anchor加NMS后处理等操作处理车道线检测&#xff0c;但这些操作或多或少会存在一些负面效应。IPM投影对深度估计和相机内外参数精度有要求&#xff0c;anchor的方式需要一些如…...

什么是UI自动化测试工具?

UI自动化测试工具有着AI技术驱动&#xff0c;零代码开启自动化测试&#xff0c;集设备管理与自动化能力于一身的组织级自动化测试管理平台。基于计算机视觉技术&#xff0c;可跨平台、跨载体执行脚本&#xff0c;脚本开发和维护效率提升至少50%;多端融合统一用户使用体验&#…...

计算顺序表中值在100到500之间的元素个数

要求顺序表中值在100到500之间的元素的个数&#xff0c;你可以使用C语言编写一个循环来遍历顺序表中的元素&#xff0c;并在循环中检查每个元素是否在指定的范围内。 #include <stdio.h>#define MAX_SIZE 100 // 假设顺序表的最大容量为100int main() {int arr[MAX_SIZE]…...

【问题总结】级数的括号可以拆吗?

问题 今天在做题的时候发现&#xff0c;括号这个问题时常出现。Σun&#xff0c;Σvn&#xff0c;和Σ&#xff08;unvn&#xff09;&#xff0c;两个级数涉及到了括号增删&#xff0c;Σ(un-1un)&#xff0c;级数钟的前后项的合并也涉及到了括号增删。 总结 添括号定理&…...

抖音自动养号脚本+抖音直播控场脚本

功能描述 一.抖音功能 1.垂直浏览 2.直播暖场 3.精准引流 4.粉丝留言 5.同城引流 6.取消关注 7.万能引流 8.精准截流 9.访客引流 10.直播间引流 11.视频分享 12.榜单引流 13.搜索引流 14.点赞回访 15.智能引流 16.关注回访 介绍下小红书数据挖掘 搜索关键词&…...

uvm中transaction的response和id的解读

在公司写代码的时候发现前辈有一段这样的代码&#xff1a; ....//其他transaction uvm_create(trans);........ uvm_send(trans); tmp_id trans.get_transaction_id(); get_response(rsp,tmp_id); 如果前面有其他transaction&#xff0c;这段代码里的get_response不带id的话…...

第四节(1):EXCEL中判断一个WORD文件是否被打开

《VBA信息获取与处理》教程(10178984)是我推出第六套教程&#xff0c;目前已经是第一版修订了。这套教程定位于最高级&#xff0c;是学完初级&#xff0c;中级后的教程。这部教程给大家讲解的内容有&#xff1a;跨应用程序信息获得、随机信息的利用、电子邮件的发送、VBA互联网…...

java.util.concurrent.locks.Condition详解

Condition翻译成中文是“条件”&#xff0c;一般我们称其为条件变量&#xff0c;每一个Condition对象都通过链表保存了一个队列&#xff0c;我们称之为条件队列。 当然了&#xff0c;这里所说的Condition对象一般指的是Condition接口的实现类ConditionObject&#xff0c;比如我…...

机器学习赋能6G近场通信:从信道估计到波束赋形的智能革命

1. 项目概述&#xff1a;当6G遇见近场&#xff0c;为何机器学习成为破局关键&#xff1f;如果你关注过5G到6G的技术演进路线&#xff0c;会发现一个核心趋势&#xff1a;天线阵列的规模正在从“大规模”走向“极大规模”。这不仅仅是数量的堆砌&#xff0c;更是通信物理原理的一…...

Tftpd32/Tftpd64不止是TFTP!手把手教你玩转它的DHCP和Syslog服务器功能

Tftpd32/Tftpd64&#xff1a;解锁DHCP与Syslog服务的隐藏潜力当大多数人提起Tftpd32/Tftpd64时&#xff0c;第一反应往往是它作为TFTP服务器的功能。这款轻量级工具确实在文件传输领域表现出色&#xff0c;但它的能力远不止于此。今天&#xff0c;我们将深入探索这款软件中两个…...

Transient、QuickEye、VerifyEye傻傻分不清?一文讲透Ansys里三种眼图仿真方法的适用场景与避坑指南

Transient、QuickEye、VerifyEye深度解析&#xff1a;Ansys眼图仿真技术选型实战指南 在高速数字系统设计中&#xff0c;眼图分析是评估信号完整性的黄金标准。面对Ansys工具链中三种截然不同的眼图生成方法&#xff0c;工程师常常陷入选择困境——是追求精确度的传统瞬态分析&…...

从BUG()到panic:深入Linux 5.4内核,看异常处理如何层层递进

从BUG()到panic&#xff1a;Linux内核异常处理的防御体系全解析当你在深夜调试一个内核模块时&#xff0c;突然屏幕刷出一串红色警告——这可能是每个Linux内核开发者都经历过的噩梦时刻。但你是否想过&#xff0c;从第一行警告出现到系统完全崩溃&#xff0c;内核究竟经历了怎…...

3步快速部署:智能茅台抢购平台的终极自动化解决方案

3步快速部署&#xff1a;智能茅台抢购平台的终极自动化解决方案 【免费下载链接】campus-imaotai i茅台app自动预约&#xff0c;每日自动预约&#xff0c;支持docker一键部署&#xff08;本项目不提供成品&#xff0c;使用的是已淘汰的算法&#xff09; 项目地址: https://gi…...

AI算法工程师如何进行模型部署?这2个工具+3个技巧,快速上线

对于软件测试从业者来说&#xff0c;模型部署并不是一个陌生的概念——随着AI功能逐渐渗透到各类应用软件中&#xff0c;测试工程师不仅需要验证模型输出的准确性&#xff0c;更需要理解部署流程对模型稳定性、响应速度和结果一致性的影响。很多测试同学会有这样的困惑&#xf…...

解决claude code频繁封号与token不足的taotoken接入方案

&#x1f680; 告别海外账号与网络限制&#xff01;稳定直连全球优质大模型&#xff0c;限时半价接入中。 &#x1f449; 点击领取海量免费额度 解决Claude Code频繁封号与Token不足的Taotoken接入方案 1. 问题背景&#xff1a;Claude Code用户面临的挑战 对于依赖Claude Cod…...

告别复杂模型:用Python+OpenCV+dlib实现简易驾驶员疲劳监测(附完整代码)

轻量级驾驶员疲劳监测系统&#xff1a;PythonOpenCVdlib实战指南 在长途驾驶或夜间行车时&#xff0c;疲劳是导致交通事故的重要因素之一。传统基于嵌入式设备的疲劳监测系统往往需要专用硬件&#xff0c;增加了开发成本和部署难度。本文将介绍如何利用Python生态中的OpenCV和d…...

基于ATmega328P与TFT屏的园艺环境监控系统:硬件选型与软件架构详解

1. 项目概述&#xff1a;打造你的家庭园艺数据监控中心如果你和我一样&#xff0c;是个喜欢在阳台或后院捣鼓花草的园艺爱好者&#xff0c;同时又对电子DIY有点兴趣&#xff0c;那么这个项目绝对会让你兴奋。我们不是在简单地种花&#xff0c;而是在用数据“聆听”植物的需求。…...

收藏2026版|大模型应用开发入门全攻略,小白程序员转行AI避坑学习指南

打算踏入大模型领域、转行AI赛道的新手与程序员&#xff0c;正式规划学习路径前&#xff0c;务必先吃透AI应用开发工程师的岗位定位与工作内容。清晰认知岗位核心价值&#xff0c;才能规避无效学习&#xff0c;精准找准发力方向。2026年大模型技术全面迈入商业化落地阶段&#…...