当前位置: 首页 > 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;比如我…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

C++ 设计模式 《小明的奶茶加料风波》

&#x1f468;‍&#x1f393; 模式名称&#xff1a;装饰器模式&#xff08;Decorator Pattern&#xff09; &#x1f466; 小明最近上线了校园奶茶配送功能&#xff0c;业务火爆&#xff0c;大家都在加料&#xff1a; 有的同学要加波霸 &#x1f7e4;&#xff0c;有的要加椰果…...

华为OD机试-最短木板长度-二分法(A卷,100分)

此题是一个最大化最小值的典型例题&#xff0c; 因为搜索范围是有界的&#xff0c;上界最大木板长度补充的全部木料长度&#xff0c;下界最小木板长度&#xff1b; 即left0,right10^6; 我们可以设置一个候选值x(mid)&#xff0c;将木板的长度全部都补充到x&#xff0c;如果成功…...

实战设计模式之模板方法模式

概述 模板方法模式定义了一个操作中的算法骨架&#xff0c;并将某些步骤延迟到子类中实现。模板方法使得子类可以在不改变算法结构的前提下&#xff0c;重新定义算法中的某些步骤。简单来说&#xff0c;就是在一个方法中定义了要执行的步骤顺序或算法框架&#xff0c;但允许子类…...

C++_哈希表

本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、基础概念 1. 哈希核心思想&#xff1a; 哈希函数的作用&#xff1a;通过此函数建立一个Key与存储位置之间的映射关系。理想目标&#xff1a;实现…...

数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)

名人说&#xff1a;莫道桑榆晚&#xff0c;为霞尚满天。——刘禹锡&#xff08;刘梦得&#xff0c;诗豪&#xff09; 原创笔记&#xff1a;Code_流苏(CSDN)&#xff08;一个喜欢古诗词和编程的Coder&#x1f60a;&#xff09; 上一篇&#xff1a;《数据结构第4章 数组和广义表》…...