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

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

InputcopyOutputcopy
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手写算法】逻辑回归实现分类(含公式推导)

公式推导&#xff1a; 代码实现&#xff1a; # 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 比赛时间 北京时间&#xff1a;2023年9月7日 18:00-2023年9月10日20:00 2 思路内容 可以参考我提供的历史竞赛信息内容&#xff0c;最新更新我会发布在博客和知乎上&#xff0c;请关注我获得最…...

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”之类的名称转换为要拨打的正确电话号码&#xff0c;而 DNS 将“www.google.com”之类的网络地址转换为托管该网站的计算机的物理 IP 地址&#xff0c;如“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&#xff0c;它在项目中最常见的就是采集Kafka中的数据然后写入HDFS或者HBase中&#xff0c;这里就是用flume采集Kafka的数据导入HDFS中 二、各工具版本 &#xff08;一&#xff09;Kafka kafka_2.13-3.0.0.tgz &#xff08;二&#xff09;…...

pnpm 升级

1. 在以下路径下删除pnpm包 2. 执行which pnpm&#xff0c;在结果目录中删除pnpm 3. sudo npm install -g pnpm 重新安装&#xff0c;node默认使用16...

有关使用HttpServletRequest的Cookie的设置和获取

文章目录 小结问题和解决参考 小结 介绍了如何在HttpServletRequest中对Cookie的进行设置和获取。 问题和解决 在服务器端的HttpServletRequest中对Cookie的进行设置后&#xff0c;客户端在接下来的请求中会携带此设置好的Cookie&#xff0c;所以可以在服务器端接收请求时提…...

关于 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 配置文件&#xff08;nginx.con…...

插入排序——希尔排序

1、简述&#xff1a; 希尔排序(Shells Sort)是插入排序的一种又称“缩小增量排序”&#xff08;Diminishing Increment Sort&#xff09;&#xff0c;是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因 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语言题目&#xff0c;最近天气炎热&#xff0c;多喝水。 NO.1 下面程序执行后&am…...

Android签名查看

查看签名文件信息 第一种方法&#xff1a; 1.打开cmd&#xff0c;执行keytool -list -v -keystore xxx.keystore&#xff0c;效果如下图&#xff1a; 第二种方法: 1.打开cmd&#xff0c;执行 keytool -list -v -keystore xxxx.keystore -storepass 签名文件密码&#xff0…...

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中智能指针的关系 内存泄漏 什么是内存泄漏&#xff1a;内存泄漏指因为疏忽或错误造成程…...

CVE-2023-3836:大华智慧园区综合管理平台任意文件上传漏洞复现

文章目录 CVE-2023-3836&#xff1a;大华智慧园区综合管理平台任意文件上传漏洞复现0x01 前言0x02 漏洞描述0x03 影响范围0x04 漏洞环境0x05 漏洞复现1.访问漏洞环境2.构造POC3.复现 CVE-2023-3836&#xff1a;大华智慧园区综合管理平台任意文件上传漏洞复现 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…...

【数学建模竞赛】预测类赛题常用算法解析

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

OFDM 系统在 AWGN 信道下对不同载波频率偏移 (CFO) 的 BER 灵敏度研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

龙虎榜——20250610

上证指数放量收阴线&#xff0c;个股多数下跌&#xff0c;盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型&#xff0c;指数短线有调整的需求&#xff0c;大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的&#xff1a;御银股份、雄帝科技 驱动…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

云原生安全实战:API网关Kong的鉴权与限流详解

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关&#xff08;API Gateway&#xff09; API网关是微服务架构中的核心组件&#xff0c;负责统一管理所有API的流量入口。它像一座…...