Nonsense Time[hdu6635] 发表于 2019-12-29 分类于 hdu 题意一个随机的排列 p,一开始所有位置都不能用。每次随机加一个位置使其变得可用,然后求当前最长上升子序列的长度。 n≤50000,T≤3 时限 14s 题解一个很重要的前置知识:长度为 n 的排列的最长上升子序列的长度的期望是 O(n) 记住就好,不会证明… 因此每个位置有 O(1n) 的概率在LIS上。 本题倒着做或许会方便一些,每次删掉一个数。 那么每次先暴力求出LIS及其位置。如果每次使其不可用的位置不在LIS上,那么不管它。否则暴力再算一遍LIS。 期望复杂度 O(n2lognn)=O(nnlogn) 这是一道用了比较重要的性质的题,在此记录一下以免忘记。 程序咕咕咕