16.5.18 考试小记

发布于 2018-05-16  2.46k 次阅读


T1 BZOJ 4662

题意略。可以发现\(L_i\)、\(R_i\)一定分别单调增,任意时刻每个人剩下的区域是一段连续区间,且区间左右端点分别单调不降。这样,我们可以维护两类集合,每类集合中的每个集合都代表左端点/右端点相同的一段连续区间。这样,每次我们只要暴力扫相邻的集合,暴力合并以及更新集合代表的左右端点即可,这样我们就可以维护一颗代表区间长度的线段树,只需要区间做减法,维护区间最小值以及最小值对应下标,就可以找到答案了。

 

T2 BZOJ 4663

说来惭愧,这道题我上次做是考场上自己YY出一个鬼畜的Tarjan然后AC了的,这一次我就直接用了题解给的思路直接连反向边,也没想想特殊情况,然后就被不能对答案产生影响的点(不能由S到达)坑掉了30。无论是啥水题都要思考一下啊。

 

T3 BZOJ 4664

一道清真的DP题目。首先,如果想摆脱后效性的话,只能从每个绝对值对答案的贡献入手,显然除了两边的元素,每个元素对和都会贡献两次绝对值(可正可负),然后就可以试着这样入手。这样直接做还是不好弄,我们可以像一些网络流的题目一样,差分贡献,最后每个位置的贡献就是真实贡献了。首先会\(h[i]\)从小到大排序,我们设\(f[i][j][k][p]\)表示加入了i个元素,这些元素形成了j段连续的区间,且当前相邻元素和尚未加入的部分贡献为k,端点个数为p的方案数。这样,就有如下转移:

设\( t = k+ (2*j-p)* (h_{i+1}-h_{i})\),即用\(t\)表示下一个贡献值(保证合法)。

当p<2时:

$$f[i][j][k][p]*(2-p) \; ->\; f[i+1][j][t][p+1] \text{ (加一个端点,和之前元素合成一段)}$$

$$f[i][j][k][p]*(2-p) \; ->\; f[i+1][j+1][t][p+1] \text{ (加一个端点,自成一段)}$$

所有情况:

$$f[i][j][k][p]*(2*j-p) \; ->\; f[i+1][j][t][p] \text{ (在空白处加一个点,和之前元素合成一段)}$$

$$f[i][j][k][p]*(j-1) \; ->\; f[i+1][j-1][t][p] \text{ (在空白处加一个点,连接两段)}$$

$$f[i][j][k][p]*(j+1-p) \; ->\; f[i+1][j+1][t][p] \text{ (在空白处加一个点,自成一段)}$$

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974