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之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
汽车生产虚拟实训中的技能提升与生产优化
在制造业蓬勃发展的大背景下,虚拟教学实训宛如一颗璀璨的新星,正发挥着不可或缺且日益凸显的关键作用,源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例,汽车生产线上各类…...
基于数字孪生的水厂可视化平台建设:架构与实践
分享大纲: 1、数字孪生水厂可视化平台建设背景 2、数字孪生水厂可视化平台建设架构 3、数字孪生水厂可视化平台建设成效 近几年,数字孪生水厂的建设开展的如火如荼。作为提升水厂管理效率、优化资源的调度手段,基于数字孪生的水厂可视化平台的…...
【python异步多线程】异步多线程爬虫代码示例
claude生成的python多线程、异步代码示例,模拟20个网页的爬取,每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程:允许程序同时执行多个任务,提高IO密集型任务(如网络请求)的效率…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
