【HDU5748 BestCoder Round 84B】【LIS模板 最长单调上升子序列】Bellovin 以尾端点最长LIS压缩数组

本文主要是介绍【HDU5748 BestCoder Round 84B】【LIS模板 最长单调上升子序列】Bellovin 以尾端点最长LIS压缩数组,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Bellovin

Accepts: 428
Submissions: 1685
Time Limit: 6000/3000 MS (Java/Others)
Memory Limit: 131072/131072 K (Java/Others)
问题描述
Peter有一个序列a_1,a_2,...,a_na1,a2,...,an. 定义F(a_1,a_2,...,a_n)=(f_1,f_2,...,f_n)F(a1,a2,...,an)=(f1,f2,...,fn), 其中f_ifi是以a_iai结尾的最长上升子序列的长度.Peter想要找到另一个序列b_1,b_2,...,b_nb1,b2,...,bn使得F(a_1,a_2,...,a_n)F(a1,a2,...,an)F(b_1,b_2,...,b_n)F(b1,b2,...,bn)相同. 对于所有可行的正整数序列, Peter想要那个字典序最小的序列.序列a_1, a_2, ..., a_na1,a2,...,anb_1, b_2, ..., b_nb1,b2,...,bn字典序小, 当且仅当存在一个正整数ii (1 \le i \le n)(1in)满足对于所有的kk (1 \le k < i)(1k<i)都有a_k = b_kak=bk并且a_i < b_iai<bi.
输入描述
输入包含多组数据, 第一行包含一个整数TT表示测试数据组数. 对于每组数据:第一行包含一个整数nn (1 \le n \le 100000)(1n100000)表示序列的长度. 第二行包含nn个整数a_1,a_2,...,a_na1,a2,...,an (1 \le a_i \le 10^9)(1ai109).
输出描述
对于每组数据, 输出nn个整数b_1,b_2,...,b_nb1,b2,...,bn (1 \le b_i \le 10^9)(1bi109)表示那个字典序最小的序列.
输入样例
3
1
10
5
5 4 3 2 1
3
1 3 5
输出样例
1
1 1 1 1 1
1 2 3

 

#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 1e5+10, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int n, a[N], d[N], f[N];
int main()
{scanf("%d", &casenum);for (casei = 1; casei <= casenum; ++casei){scanf("%d", &n);for (int i = 1; i <= n; ++i)scanf("%d", &a[i]);int len = 0; d[0] = -1e9;for (int i = 1; i <= n; ++i){if (a[i] > d[len])d[++len] = a[i], f[i] = len;else{int l = 1;int r = len;while (l < r){int mid = (l + r) >> 1;if (a[i] <= d[mid])r = mid;else l = mid + 1;}d[l] = a[i];f[i] = l;}printf("%d%c", f[i], i == n ? '\n' : ' ');}}return 0;
}
/*
【trick&&吐槽】
比赛的时候把f[i]求成了a[i]加入数组之后的LIS,导致了一次WA,囧【题意】
有n(1e5)个数a[]
用fa[i]表示以a[i]为尾端点的LIS
让你用最小字典序的正整数序列b[]代替a[]使得以b[]为尾端点的LIS fb[]恰好等于fa[]【类型】
LIS【分析】
我们直接求出f[],f[]就是答案>.<
注意f[i]代表的是以i为尾端点的LIS哦【时间复杂度&&优化】
O(nlogn)【数据】
10
2 3 4 5 6 1 2 3 4 7*/


这篇关于【HDU5748 BestCoder Round 84B】【LIS模板 最长单调上升子序列】Bellovin 以尾端点最长LIS压缩数组的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/610386

相关文章

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

Python实现将MySQL中所有表的数据都导出为CSV文件并压缩

《Python实现将MySQL中所有表的数据都导出为CSV文件并压缩》这篇文章主要为大家详细介绍了如何使用Python将MySQL数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到... python将mysql数据库中所有表的数据都导出为CSV文件到一个目录,并压缩为zip文件到另一个

C++从序列容器中删除元素的四种方法

《C++从序列容器中删除元素的四种方法》删除元素的方法在序列容器和关联容器之间是非常不同的,在序列容器中,vector和string是最常用的,但这里也会介绍deque和list以供全面了解,尽管在一... 目录一、简介二、移除给定位置的元素三、移除与某个值相等的元素3.1、序列容器vector、deque

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动