Day7

【最长上升子序列】
题意:对一个序列进行操作,可以在序列最后加上一个数,可以回到k时的序列,求每次操作后序列的最长上升子序列长度。
【LIS求法】:通常求最长上升子序列都是n^2动规,当n较大时便要考虑nlogn的算法。
设f[k]表示长度为k的LIS最末尾的元素,易知f是单调递增的,对于新加入的x,如果f[k] < x, 意味着最长上升子序列的长度可以加1。如果f[k] > x,那么 对于f[i] > x > f[i - 1]考虑f第i位的值哪个更优?显然要取x。求i可以用二分优化,LIS便能在nlongn的时间内求出。
这题需要回到第k时的序列,由上述算法可知,对于操作j、j - 1,f数组的变化只有一个数,于是用可持久化线段树来维护这个数组,使修改和查询的时间变成logn, 时间复杂度是O(nlog^2n)。
由于时间复杂度和空间复杂度与题目要求十分相近,要考虑常数与每个结点的线段树子节点数量。
正解对于每个回到k序列的操作建一棵树,直接在这棵树上跑LIS,时间复杂度O(nlogn)。
【图的X匹配】
题意:对于一个多边形,使取出的边没有交点(即没有相邻的边)的方案数。
打表可以发现答案的规律类似斐波那契数列, 由于没有取模, 需要用高精度完成加法操作, n的值最大为10000, 最好用滚动数组。
证明:
【努力】
题意:使n个点形成一棵树的连边方法。
由prufer数列可得n个点的无向图有n^(n-2)种, n个点的树有n-1条边,答案便是n^(n-2)*(n-1)!。

代码如下:

继续阅读Day7