23ccpc(最长上升子序列题解)
你原本有一个 1 到 n 的排列但是不慎地你遗忘了它但是你记得以 第i个位置 结尾的最长上升子序 列的长度数组 an 现在希望你能够构造一个符合条件的排列 p 如果不存在符合上述条件的排列 p 则输出 −1。 这里定义以 第i位置 结尾的最长上升子序列的长度为符合以下条件的整数数组 id 中 k 的最大值。
1 ≤ id1 < id2 < id3 < · · · < idk = i pid1 < pid2 < pid3 < · · · < pidk 本题输入输出量比较大请选手注意。
Input 第一行一个整数 n (1 ≤ n ≤ 106) 第二行 n 个整数表示数组 an (1 ≤ ai ≤ n)其中 ai 表示以 i 结尾的最长上升子序列的长度。
Output 一行 n 个整数表示排列 p ,如果无解则输出 −1。
思路:
首先判断有没有符合的子序列,可以发现如果第a[i]为k,说明前边一定有子序列长度达到k-1,我们可以记录前i个a的最大值,如果a[i]>k+1,那么就没有这样的子序列。
如果有,有相同长度的子序列,如果j>i,那么p[j]<p[i],然后根据子序列长度我们可以将1-n分成几份,然后根据序列长度,我让长的子序列拥有更大的值;
举个例子:
5
1 2 2 3 3
长度为3的子序列有两个,长度为2的子序列有两个,长度为1的子序列有1个。
我让3对应的位置上值为5,4(从大到小)
2对应的位置上值为3,2
1对应位置上值为1
整个序列为:
1 3 2 5 4
我们可以事先求出相同序列长度对应的最大值,然后从前往后遍历,输出一种序列在当前位置的值后,让值-1,接着往后遍历即可。
代码:
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<unordered_map>
#include<map>
using namespace std;
typedef long long LL;
#define per(i,a,b) for(int i=a;i<=b;i++)
#define ber(i,a,b) for(int i=a;i>=b;i--)
const int N = 1e6 + 100;
int a[N],cn[N],ans[N],p[N];
int n;
int main()
{
cin >> n;
per(i, 1, n)
{
scanf("%d", &a[i]);
cn[a[i]]++;
}
int flag = 0, cnt = 0;
per(i, 1, n)
{
if (a[i] > cnt + 1)
{
flag = 1;
break;
}
else if (a[i] == cnt + 1)
cnt++;
}
if (flag)
{
cout << -1 << endl;
return 0;
}
cnt =n;
ber(i, n, 1)
{
if (cn[i])
{
p[i] = cnt;
cnt = cnt - cn[i];
}
}
per(i, 1, n)
{
ans[i] = p[a[i]];
p[a[i]]--;
}
for (int i = 1; i <= n-1; i++)
printf("%d ", ans[i]);
printf("%d\n", ans[n]);
return 0;
}
相关文章:
23ccpc(最长上升子序列题解)
你原本有一个 1 到 n 的排列但是不慎地你遗忘了它但是你记得以 第i个位置 结尾的最长上升子序 列的长度数组 an 现在希望你能够构造一个符合条件的排列 p 如果不存在符合上述条件的排列 p 则输出 −1。 这里定义以 第i位置 结尾的最长上升子序列的长度为符合…...
BUUCTF easycap 1
BUUCTF:https://buuoj.cn/challenges 题目描述: 下载附件,解压得到一个.pcap文件。 密文: 解题思路: 1、这道题和它的名字一样,真的很easy。双击easycap.pcap文件,打开Wireshark。在Wireshark中…...
[LeetCode]-160. 相交链表-141. 环形链表-142.环形链表II-138.随机链表的复制
目录 160.相交链表 题目 思路 代码 141.环形链表 题目 思路 代码 142.环形链表II 题目 思路 代码 160.相交链表 160. 相交链表 - 力扣(LeetCode)https://leetcode.cn/problems/intersection-of-two-linked-lists/description/ 题目 给你两个…...
聊一聊关于手机Charge IC的电流流向
关于手机Charge,小白在以前的文章很少讲,一是这部分东西太多,过于复杂。二是总感觉写起来欠缺点什么。但后来想一想,本是抱着互相学习来写文章的心理态度,还是决定尝试写一些。 关于今天要讲的关于手机Charge的内容&a…...
【k8s】pod调度——亲和,反亲和,污点,容忍
官方网址:https://kubernetes.io/zh/docs/concepts/scheduling-eviction/assign-pod-node/ 一、亲和性 (1)节点亲和性 pod.spec.nodeAffinity ●preferredDuringSchedulingIgnoredDuringExecution:软策略 p开头 ●requiredDuri…...
分享者 - 携程旅游创作者搬砖项目图文教程
大家好!携程这个出行旅游平台相信大家都不陌生吧。 每天都有大量的旅客在里面浏览攻略,寻找灵感和旅游建议。 那么,我们的项目就是把一些优质的小红书平台上的旅游攻略或作品,经过处理后搬运到携程平台上发布。 这个项目如何操作呢…...
vite配置.env环境变量文件,开发环境,测试环境,预发布环境,生产环境
在vue2,用的vue-cli脚手架搭建项目,cli用的是webpack 当你yarn dev时,命令会启动package.json中的dev键名的值,也就是后面的一行命令 这时浏览器会去识别你是开发环境还是生产环境,其实windows是不能直接识别你是开发…...
0003Java安卓程序设计-springboot基于Android的学习生活交流APP
文章目录 **摘** **要**目 录系统设计开发环境 编程技术交流、源码分享、模板分享、网课教程 🐧裙:776871563 摘 要 网络的广泛应用给生活带来了十分的便利。所以把学习生活交流管理与现在网络相结合,利用java技术建设学习生活交流APP&…...
Java8 时间字符串校验是否为对应的日期格式
时间字符串格式校验 严格模式下校验日期字符串 public static boolean isDateStrict(String dateStr, String pattern) {try {DateTimeFormatter formatter new DateTimeFormatterBuilder().appendPattern("yyyyMMdd").parseDefaulting(ChronoField.ERA, 1).toFor…...
2023.11.6联赛总结
T 1 T1 T1让你构造出一个不超过 40 ∗ 40 40*40 40∗40的矩阵,满足连续的 r y x ryx ryx有 n n n个。 一开始我想着直接放 r y x ryx ryx,这个做法有 80 80 80分,但是打挂了,再调了将近1个小时后,选择先跳过ÿ…...
UE5——源码阅读——9——引擎预初始化
加载项目模块 判断项目是否是有意义的 准备读取模块 对应着错误信息 广播 加载插件模块 根据配置是否已经启用插件 开始遍历所有的插件 尝试读取插件 检查上一次完成的加载阶段是否大于当前的加载阶段 通知加载完成...
报错Could not resolve placeholder ‘driver‘ in value “${driver}“
这是我的报错: 原因是我的applicationContext.xml文件加载properties文件径错误: 应该把路径改成这样就可以了:...
Rust编程基础核心之所有权(下)
1.变量与数据交互方式之二: 克隆 在上一节中, 我们讨论了变量与数据交互的第一种方式: 移动, 本节将介绍第二种方式:克隆。 如果我们 确实 需要深度复制 String 中堆上的数据,而不仅仅是栈上的数据,可以使用一个叫做 clone 的通用函数。 看下面的代码…...
高防CDN:企业网络安全的坚强后盾
随着互联网的快速发展,企业的网络面临着越来越多的安全威胁。在这种背景下,高防CDN(Content Delivery Network)已经成为了企业网络安全的坚强后盾。本文将理性分析高防CDN对于企业发展的影响,强调其在维护网络稳定性、…...
gitlab 设置 分支只读
一,设置master分支只读, 并且只有Maintainers 拥有合并权限。 二,设置成员权限 改为developer 三,邀请成员 点击右上角 Invite Members...
Spring Boot 面试题——常用注解
目录 Spring Bean将一个类声明为 Bean自动装配 Bean声明 Bean 的作用域 前端后传值处理常见的 HTTP 请求类型读取配置文件定时任务全局 Controller 层异常处理 Spring Bean 将一个类声明为 Bean Component:通用的注解,可标注任意类为 Spring 组件。如果…...
RabbitMQ(高级特性) 设置队列所有消息存活时间
RabbitMQ可以设置消息的存活时间(Time To Live,简称TTL),当消息到达存活时间后还没有被消费,会被移出队列。RabbitMQ可以对队列的所有消息设置存活时间,也可以对某条消息设置存活时间。 Configuration pub…...
刷题学习记录
[MRCTF2020]PYWebsite1 进入环境,页面就提示要购买flag,不要想着购买,因为扫码后提示的是一个文本 “拜托!你不会真的想PYflag吧,这样可是违规的!再好好分析一下界面代码吧” 查看网页源码,发现…...
WPF中依赖属性及附加属性的概念及用法
完全来源于十月的寒流,感谢大佬讲解 依赖属性 由依赖属性提供的属性功能 与字段支持的属性不同,依赖属性扩展了属性的功能。 通常,添加的功能表示或支持以下功能之一: 资源数据绑定样式动画元数据重写属性值继承WPF 设计器集成 …...
Golang爬虫封装
引言 爬虫是一种自动化地从网页中提取信息的程序,它在现代互联网的数据获取和分析中扮演着重要的角色。Golang作为一门强大的编程语言,也提供了丰富的工具和库来实现爬虫功能。在本文中,我们将探讨如何使用Golang来封装一个灵活、高效的爬虫…...
class文件加载到内存
JVM将class文件加载到内存的过程主要分为三个阶段:加载(Loading)、链接(Linking)和初始化(Initialization),其中链接又细分为验证、准备、解析三个步骤 。 一、加载(…...
Vivado Design Suite中BUFG优化策略与实战技巧
1. 理解BUFG的核心作用与设计痛点 在FPGA设计中,时钟信号就像人体神经系统中的电脉冲,需要快速、准确地传递到每个功能单元。BUFG(全局时钟缓冲器)就是Xilinx器件中专用的"信号放大器",它能将时钟信号分配到…...
Qwen3.5-9B多场景应用:心理咨询对话记录分析+情绪倾向识别案例
Qwen3.5-9B多场景应用:心理咨询对话记录分析情绪倾向识别案例 1. 项目概述 Qwen3.5-9B是一款拥有90亿参数的开源大语言模型,具备强大的逻辑推理、代码生成和多轮对话能力。该模型特别适合处理心理咨询对话记录分析任务,能够准确识别对话中的…...
MySQL
我目前正在学习SQL语句,我所了解到的MySQL其实是一堆服务器,在下载服务器的时候,可以选择下载一些客户端,MySQL会自带一些客户端,像类似于终端的小黑框,还有什么bench;我还是喜欢外观好看的客户端 !我学SQL语句目前学到了数据类型,有数值型的,字符型的,二进制型的,值得一提的是…...
聚点智行:WorkBuddy 辅助开发 AI 地图智能应用实战
一、从痛点到创意:一个真实场景的启发 作为一名经常组织朋友聚会的"社交达人",我遇到了一个看似简单却让人头疼的问题:每次约饭,大家都在问"在哪见?" 张三住在回龙观,李四在东直门&…...
实战指南:基于快马AI生成可部署的、支持多游戏与数据库的账号管理应用
今天想和大家分享一个实战项目:用Python开发一个支持多游戏的账号管理器(俗称"lv上号器")。这个工具特别适合游戏多开玩家,能安全存储不同游戏的账号信息,还能一键登录不同游戏客户端。 项目需求分析 首先明…...
工程伦理案例分析:从经典失败项目看责任分配与风险预防
工程伦理案例分析:从经典失败项目看责任分配与风险预防 当一座桥梁在通车典礼上轰然倒塌,当一栋新建大楼在台风中支离破碎,这些触目惊心的工程事故背后,往往隐藏着复杂的伦理困境。工程伦理不是简单的对错判断题,而是需…...
Doris集群部署避坑指南:3FE+3BE配置全流程(含Java环境配置与常见问题解决)
Doris集群部署实战:3FE3BE高可用架构搭建与深度调优 在企业级数据分析场景中,Doris凭借其出色的实时分析性能和高并发处理能力,已成为众多企业的首选OLAP引擎。本文将基于3FE(Frontend)3BE(Backend…...
理解usearch的动态内存调整:实现高效向量搜索的终极指南
理解usearch的动态内存调整:实现高效向量搜索的终极指南 【免费下载链接】usearch Fast Open-Source Search & Clustering engine for Vectors & Arbitrary Objects in C, C, Python, JavaScript, Rust, Java, Objective-C, Swift, C#, GoLang, and Wolfr…...
别再只会让舵机转圈了!用Arduino和SG90实现精准角度控制的保姆级教程
从转圈到精准控制:Arduino与SG90舵机的高级应用指南 第一次接触舵机时,我们往往满足于让它简单地来回转动——这确实很有趣,就像给玩具注入了生命。但当你真正想用它构建一个机械臂、智能云台或是自动喂食器时,这种粗放的控制方式…...
