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

分块算法

【思想】  分块思想的核心是将一个集合划分成若干个规模较小的子集。即让连续的序列组成一个块,便于进行处理。
为了便于处理,分块需要满足:
(1) 若子集规模很小, 对每个子集可使用关于子集规模的复杂度较高的算法。
(2) 若子集数目很少, 可以使用与整个集合规模有关的算法分别处理每个子集。
可以发现前两条性质其实是相互矛盾的, 因此为了均衡, 我们既不能让子集规模过大,
也不能让子集数目过大, 通常分块的大小都取n^0.5(根号n)。
通过预处理每一个分块,对于询问的区间,我们可以把其分为完全处于块中的区间与不完全处于块中的区间。完全处于块中的区间可以用预处理的结果得出答案,不完全处于块中的区间采用暴力枚举的方法。由于每个块的大小有限,所以枚举的时间复制度并不大。这样,算法的时间复杂度是O(n^0.5 * n)。
【优点】 分块算法的时间复杂度比一些数据结构的O(n logn)还大,那分块算法有什么用呢。但是,有些数据是普通的数据结构不能合并的,比如BZOJ2724: [Violet 6]蒲公英
题目大意是给定 n 个数, 每次询问区间[L, R]内的众数, 强制在线。
很明显,这题是用线段树不能解决的。分块算法则能很好的完成。
在此题中我们就预处理出两个量: cnt[i][j]表示i 这个元素在前 j 块中的出现次数,以及 ans[i][j] 表示第i 块到第 j 块这个区间的众数。这两个量都是能在 O(n^0.5)的时间内预处理出来的。 cnt[i][j]较为简单就不赘述; 求 ans[i][j] 时我们先枚举并固定 i , 当 i 确定后我们用一个数组来记录每个数字的出现次数, 初始时所有数字出现次数均为 0。 接着我们从第i 块左端点开始, 枚举之后的所有元素, 并更新出现次数的数组, 在这个程中我们是能求出当前众数的。 当枚举到的元素是某个块 j 的右端点时, 我们就知道 ans[i][j] 的值了, 不难发现这个做法复杂度是 O(n^0.5)的。

而对于询问,先找出完全被包含的分块,此时,答案要么是这些分块的众数,要么是不完全被包含的分块中的数。我们可以暴力将它们全部枚举一遍, 记录下它们当前的出现次数, 配合之前预处理的 cnt[i][ j], 我们可以快速的算出一个数在第 L 块到第 R 块间的出现次数, 加上它在那 O( n^0.5) 个单个元素中出现的次数, 就是它在询问区间内出现的总次数, 进而我们可以利用它来更新答案。

代码如下:

继续阅读分块算法

[BZOJ 2743] [HEOI 2012] 采花

树状数组 + 差分

看上去就像莫队算法。

然后发现数据有点大......算了。

可以发现每种花只有当前区间中的第二枝对后面有贡献。则计算答案可以利用差分方法:若在 pos 位置的一束花能对后方产生贡献,则在树状数组中将 [pos, n] 区间 +1。最终此时某个区间答案即为区间和。

记录下位置 i 后第一次出现该位置颜色花的位置 nxt[i]。考虑从一个区间 [L, R] 到另一个区间 [L+1, R] 答案的变化:既然位置 L 处的花退出了区间,那么花 i 对答案的影响也要被去除,即在树状数组中把 [L, n] 答案 -1。原本 nxt[i] 位置的花是区间内第二朵花,现在也变成了第一朵,因此更新答案,[nxt[i], n] 区间 +1。

既然知道了相邻区间的转移,那么整体的做法也可以明确了:先将读入的所有区间按左端点排序,然后按刚才的方法在左端点间一位一位转移,答案就是区间和了。

代码如下:

继续阅读[BZOJ 2743] [HEOI 2012] 采花