Nonsense Time[hdu6635]

题意

一个随机的排列 p,一开始所有位置都不能用。每次随机加一个位置使其变得可用,然后求当前最长上升子序列的长度。

n50000,T3

时限 14s

题解

一个很重要的前置知识:长度为 n 的排列的最长上升子序列的长度的期望是 O(n)

记住就好,不会证明…

因此每个位置有 O(1n) 的概率在LIS上。

本题倒着做或许会方便一些,每次删掉一个数。

那么每次先暴力求出LIS及其位置。如果每次使其不可用的位置不在LIS上,那么不管它。否则暴力再算一遍LIS。

期望复杂度 O(n2lognn)=O(nnlogn)

这是一道用了比较重要的性质的题,在此记录一下以免忘记。

程序

咕咕咕