Day2

【曲线】
题意:令f(x)为多个二次(一次)函数的最大值,求f(x)的最小值。
画图可以发现两个二次函数取最大值的图像形状类似二次函数,可得f(x)的图像也类似二次函数。那么,可以在所给区间内用三分求出答案。
二分也可完成此题,二分答案ans,暴力判断每个二次函数<=ans的区间是否有交集,若有,则答案可行,反之答案不可行。

【挑战】

题意:将字符串分块,使每个块中的字母都在下一个块中出现过。(即下一块每个字母的出现次数比当前块多)。求最多的分块。
令f[i][j]表示在i位是最后一个块的长度为j的答案。可由f[i - j][k]转移得到。时间复杂度为O(n ^ 3)。可得70分。
改进这个算法,因为要求块最多,应用贪心的思想,每个块的长度越少,块的数量越多。令f[i]表示以i为结尾最后一块的长度最短是多少。可以由f[i - f[i]]转移得到。

【序列】

题意:判断序列的所有子序列是否都有数只出现一次。
暴力枚举每个子序列,判断是否符合条件,可得30分。
改进暴力,对于一个a[i],前一次出现记为pre[i],后一次出现记为nex[i]。那左端点l在pre[i]+1..i,右端点在i..nex[i]-1都是合法的。如果判定一个区间[l,r],a[i]是其中唯一出现过的数字。那这个区间就可以切割成判定2个区间[l,i - 1],[i + 1, r]。那对于一个区间[l,r],i,j同时从左边和右边开始扫,碰到第一个唯一出现的数字就切割。直到l>=r。
这种做法看起来很像暴力,但实际上跑得飞快。时间复杂度证明:T(n) = T(k) + T(n-k)+min(n, n - k)。一种直观的想法就是,每次复杂度都是较小的那个区间。倒过来看相当于较小的合并到较大的。那就是启发式合并。O(nlogn)。

主要代码如下:

继续阅读Day2