模拟50 题解

A. 施工

又是利用了一些结论的题,因为想不到结论,经常做不出这种题。

枚举两个不变的边界,那么中间的建筑必定被提高成相同的小于等于边界的高度。

于是设$f_i$表示考虑前i个建筑,并且第i个建筑高度不变的最优答案。

设对于转移(i,j),中间建筑的最优高度为t,可以写出dp转移方程。

拆开式子,可以得到一个二次函数。

直接求二次函数最值,可以做到$O(n^2)$。

接着发现很多的转移是无效的,因为转移(i,j)要满足:

任取$i<k<j$,$h(k)<=h(i)$,$h(k)<=h(j)$。

可以维护一个由栈顶到栈底单调递增的单调栈,以维护转移的位置。

需要学习的是特殊的打法,用栈顶表示(i,j)范围内最大的元素,而栈顶-1表示决策点。

B. 蔬菜

正解还是用到了分块的思想:

1.对于出现次数很多的蔬菜,直接用前缀和累计答案。

2.对于出现次数较少的蔬菜,考虑将平方的含义转化为点对。

将一棵蔬菜定义为点$(x,y)$,那么任意相同的两棵蔬菜(可以是同一个棵)可以表示为点对$(x_1,x_2,y_1,y_2)$。

设询问为$(x,y)(X,Y)$,即统计有多少个点对满足:

限制(1):$x<=x_1<=X$  

限制(2):$x<=x_2<=X$

限制(3):$y<=y_1<=Y$  

限制(4):$y<=y_2<=Y$

四维偏序问题,可以暴力四维前缀和容斥。

然而空间复杂度$O(n^4)$,开不下。

考虑离线询问,并且将每个询问对于限制(1)拆为两个,即$ans_X-ans_{x-1}$。

将所有点对按$x_1$排序,所有询问按拆成的第一维限制排序。

那么对于每个询问,单调指针不断添加点对到三维数状数组里,

添加完后大力三维容斥统计答案就可以了。

 

设蔬菜由出现次数决定使用哪种算法统计的分界值为k,

那么本题的复杂度为$O(n^2*frac{n^2}{k})$(对每种大于k的蔬菜预处理)

+$O(n^2*k*log^3n)$(每种蔬菜都恰好接近k个的时候,总的点对最多,对这些点对的预处理)

+$O(q*(frac{n^2}{k}+log^3n))$(每次询问对于两部分的查询)

由均值不等式,可以得到当$k=sqrtfrac{n^2+q}{log^3n}$时取得最优的复杂度。

 

另外记yxs巨神不用容斥的做法:

将每一个点对$(x_1,x_2,y_1,y_2)$化作点$(x_1,y_1)$在点$(x_2,y_2)$左上方的形式。

那么询问的限制转化为:

$x<=x_1$  $x_2<=X$

$y<=y_1$  $y_2<=Y$

因为$x_1$已经排序,自动满足限制。

$x_2$,$y_2$都是小于等于某个值的限制,只要将$y_1$翻转就可以直接查三维前缀和统计答案。

C. 联盟

可以说是三道题里最简单的一道。

首先,题中定义的危险程度,树上最远两点距离,即树的直径。

那么问题被转化成割掉树上一条边,求如何用一条边连接两棵树使新树的直径最小。

显然最优决策一定是连上两棵新树的直径中点,因为任何改变位置都会使新树的直径更长。

于是问题转化成如何求原树上,割掉一条边之后两棵新树的直径。

正常的思路都是选节点1作为根节点,进行dfs求出子树直径。

然而问题是,有一些联通块无法被1的子树表示出来。

那么考虑转化思路,我们分别以树上一条直径的两个端点作为根节点,求出子树的直径。

于是分类讨论就可以了:

1.割掉非直径边:那么直径所在联通块的直径就是原树的直径,另一侧的直径可以被任意一个dp数组表示出来。

2.割掉直径边:那么两个dp数组分别表示一个联通块的直径。

最后随便选一条符合的答案,抽出两条直径连中点就可以了。

原文地址:https://www.cnblogs.com/skyh/p/11573202.html