A - Orac and Models(最长上升子序列——加强版)
There are nn models in the shop numbered from 11 to nn, with sizes s_1, s_2, \ldots, s_ns1,s2,…,sn.
Orac will buy some of the models and will arrange them in the order of increasing numbers (i.e. indices, but not sizes).
Orac thinks that the obtained arrangement is beatiful, if for any two adjacent models with indices i_jij and i_{j+1}ij+1 (note that i_j < i_{j+1}ij<ij+1, because Orac arranged them properly), i_{j+1}ij+1 is divisible by i_jij and s_{i_j} < s_{i_{j+1}}sij<sij+1.
For example, for 66 models with sizes \{3, 6, 7, 7, 7, 7\}{3,6,7,7,7,7}, he can buy models with indices 11, 22, and 66, and the obtained arrangement will be beautiful. Also, note that the arrangement with exactly one model is also considered beautiful.
Orac wants to know the maximum number of models that he can buy, and he may ask you these queries many times.
Input
The first line contains one integer t\ (1 \le t\le 100)t (1≤t≤100): the number of queries.
Each query contains two lines. The first line contains one integer n\ (1\le n\le 100\,000)n (1≤n≤100000): the number of models in the shop, and the second line contains nn integers s_1,\dots,s_n\ (1\le s_i\le 10^9)s1,…,sn (1≤si≤109): the sizes of models.
It is guaranteed that the total sum of nn is at most 100\,000100000.
Output
Print tt lines, the ii-th of them should contain the maximum number of models that Orac can buy for the ii-th query.
Sample 1
Inputcopy | Outputcopy |
---|---|
4 4 5 3 4 6 7 1 4 2 3 6 4 9 5 5 4 3 2 1 1 9 | 2 3 1 1 |
Note
In the first query, for example, Orac can buy models with indices 22 and 44, the arrangement will be beautiful because 44 is divisible by 22 and 66 is more than 33. By enumerating, we can easily find that there are no beautiful arrangements with more than two models.
In the second query, Orac can buy models with indices 11, 33, and 66. By enumerating, we can easily find that there are no beautiful arrangements with more than three models.
In the third query, there are no beautiful arrangements with more than one model.、、
题目翻译:
给出n个数的值,求出满足下标j整除i并且a[j]>a[i]的最多个数(j>i)
#include<iostream>
#include<algorithm>
#include<map>
#include<cstring>
#include<vector>
#include<cmath>
#include<cstdlib>using namespace std;
const int N = 1e5 + 10;int a[N],b[N];//DP:b[i]表示以i结尾的子序列的长度int main()
{int t; cin >> t;while (t--){int n; cin >> n;for (int i = 1; i <= n; i++) cin >> a[i]; //读入数据for (int i = 1; i <= n; i++) b[i] = 1;for (int i = 1; i <= n; i++)for (int j = 2 * i; j <= n; j += i) //满足条件1:j是i的倍数,j可以整除iif (a[i] < a[j]) b[j] = max(b[j], b[i] + 1); //满足条件2:a[j]>a[i]//DP:以选不选第j个数作为比较,求最大的那个//选j:长度为j的上一个数i加1,即b[i]+1;//不选j:即b[j]int ans = -INT_MAX;for (int i = 1; i <= n; i++) ans = max(ans, b[i]);cout << ans << endl;}}
相关文章:
A - Orac and Models(最长上升子序列——加强版)
There are nn models in the shop numbered from 11 to nn, with sizes s_1, s_2, \ldots, s_ns1,s2,…,sn. Orac will buy some of the models and will arrange them in the order of increasing numbers (i.e. indices, but not sizes). Orac thinks that the obtai…...

【python手写算法】逻辑回归实现分类(含公式推导)
公式推导: 代码实现: # codingutf-8 import matplotlib.pyplot as plt import numpy as npdef f(w1,x1,w2,x2,b):zw1*x1w2*x2breturn 1/(1np.exp(-z)) if __name__ __main__:X1 [12.46, 0.25, 5.22, 11.3, 6.81, 4.59, 0.66, 14.53, 15.49, 14.43,2.1…...

【2023高教社杯数学建模国赛】ABCD题 问题分析、模型建立、参考文献及实现代码
【2023高教社杯数学建模国赛】ABCD题 问题分析、模型建立、参考文献及实现代码 1 比赛时间 北京时间:2023年9月7日 18:00-2023年9月10日20:00 2 思路内容 可以参考我提供的历史竞赛信息内容,最新更新我会发布在博客和知乎上,请关注我获得最…...

yum安装mysql5.7散记
## 数据源安装 $ yum -y install wget $ wget http://dev.mysql.com/get/mysql57-community-release-el7-8.noarch.rpm $ yum localinstall mysql57-community-release-el7-8.noarch.rpm $ yum repolist enabled | grep "mysql.*-community.*" $ yum install mysql-…...

DNS解析
1.DNS介绍 DNS 表示域名系统。此系统实质上是用于整理和识别各个域名的网络电话簿。电话簿将“Acme Pizza”之类的名称转换为要拨打的正确电话号码,而 DNS 将“www.google.com”之类的网络地址转换为托管该网站的计算机的物理 IP 地址,如“74.125.19.147…...
从jdk8 升级到jdk17的问题总结
目录 1. java.lang.reflect.InaccessibleObjectException: 2. java.lang.UnsatisfiedLinkError in autosys 3. java.lang.NoClassDefFoundError: Could not initialize class net.sf.jasperreports.engine.util.JRStyledTextParser 4. java.lang.UnsatisfiedLinkError: **…...

一百七十二、Flume——Flume采集Kafka数据写入HDFS中(亲测有效、附截图)
一、目的 作为日志采集工具Flume,它在项目中最常见的就是采集Kafka中的数据然后写入HDFS或者HBase中,这里就是用flume采集Kafka的数据导入HDFS中 二、各工具版本 (一)Kafka kafka_2.13-3.0.0.tgz (二)…...

pnpm 升级
1. 在以下路径下删除pnpm包 2. 执行which pnpm,在结果目录中删除pnpm 3. sudo npm install -g pnpm 重新安装,node默认使用16...
有关使用HttpServletRequest的Cookie的设置和获取
文章目录 小结问题和解决参考 小结 介绍了如何在HttpServletRequest中对Cookie的进行设置和获取。 问题和解决 在服务器端的HttpServletRequest中对Cookie的进行设置后,客户端在接下来的请求中会携带此设置好的Cookie,所以可以在服务器端接收请求时提…...
关于 Nginx 的哪些事
关于 Nginx 的哪些事 1、Nginx 主要功能2、Nginx 的常用命令2.1、启动Nginx2.2、停止 Nginx2.3、重新加载Nginx 配置2.4、检查Nginx配置文件2.5、指定配置文件2.6、检查Nginx版本2.7、显示Nginx帮助信息 3、Nginx 配置文件 nginx.conf3.1、Nginx 配置文件(nginx.con…...

插入排序——希尔排序
1、简述: 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。 希尔排…...

C语言之初阶总结篇
目录 NO.1 NO.2 NO.3 NO.4 NO.5 NO.6 NO.7 NO.8 NO.9 NO.10 NO.11 NO.12.概念tips NO.13.求最小公倍数 NO.14.最大公因数 NO.15.输入读取字符串 NO.16.倒置字符串 今天是一些C语言题目,最近天气炎热,多喝水。 NO.1 下面程序执行后&am…...

Android签名查看
查看签名文件信息 第一种方法: 1.打开cmd,执行keytool -list -v -keystore xxx.keystore,效果如下图: 第二种方法: 1.打开cmd,执行 keytool -list -v -keystore xxxx.keystore -storepass 签名文件密码࿰…...
Educational Codeforces Round 3
目录 A. USB Flash Drives B. The Best Gift C. Load Balancing D. Gadgets for dollars and pounds A. USB Flash Drives #include<bits/stdc.h>using namespace std; const int N1e65; typedef long long ll; typedef pair<ll,ll> pll; typedef array<int…...
Docker Compose常用命令
常用命令 1.1 restart, start, stop-- 启动和停止服务 命令必须在 docker-compose.yml文件所在的目录下执行。 # 前台启动, 启动项目中的所有服务。 $. docker-compose up# 后台启动, 启动所有服务并在后台运行。 $. docker-compose up -d# 停止所有服务。 $. docker-compose …...

C++——智能指针
智能指针 文章目录 智能指针内存泄漏智能指针解决内存泄漏问题智能指针的使用及原理RAII智能指针对象的拷贝问题 C中的智能指针auto_ptrunique_ptrshared_ptrweak_ptr定制包装器C11和boost中智能指针的关系 内存泄漏 什么是内存泄漏:内存泄漏指因为疏忽或错误造成程…...

CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现
文章目录 CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现0x01 前言0x02 漏洞描述0x03 影响范围0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现 0x01 前言 免责声…...

LAMP搭建WordPress
L linux A apache hhtpd M mysql/maridb P PHP1、 安装php yum -y install php php-fpm php-server php-mysql1.1、 启动php-fpm并自启 systemctl enable php-fpm --now[rootecs-1cee ~]# systemctl status php-fpm ● php-fpm.service - The PHP FastCGI Process ManagerLoa…...

【数学建模竞赛】预测类赛题常用算法解析
解析常见的预测类算法 灰色预测模型 灰色预测模型是一种利用少量的、不完全的信息,建立数学模型并进行预测的方法。该方法通过对系统行为特征的发展变化规律进行估计预测,同时也可以对行为特征的异常情况发生的时刻进行估计计算,并研究特定…...

OFDM 系统在 AWGN 信道下对不同载波频率偏移 (CFO) 的 BER 灵敏度研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...
MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例
一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)
引言:为什么 Eureka 依然是存量系统的核心? 尽管 Nacos 等新注册中心崛起,但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制,是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...
CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云
目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...

优选算法第十二讲:队列 + 宽搜 优先级队列
优选算法第十二讲:队列 宽搜 && 优先级队列 1.N叉树的层序遍历2.二叉树的锯齿型层序遍历3.二叉树最大宽度4.在每个树行中找最大值5.优先级队列 -- 最后一块石头的重量6.数据流中的第K大元素7.前K个高频单词8.数据流的中位数 1.N叉树的层序遍历 2.二叉树的锯…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
2023赣州旅游投资集团
单选题 1.“不登高山,不知天之高也;不临深溪,不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...