Difference between revisions of "2019 ECNU XCPC March Selection"

From EOJ Wiki
Jump to navigation Jump to search
(Blanked the page)
 
Line 1: Line 1:
==Problem A==
 
  
考虑学生上车时间点,我们令 $dp_i$ 代表在 $i$ 时刻发车时,前面所有学生等待时间的和的最小值。不难发现,我们可以通过 $dp_{i-2 \times m+1}$ ~ $dp_{i-m}$ 推出 $dp_i$(如果发车间隔大于等于 $2 \times m$,可以视作在中间发了一部空车,不影响 $dp$ 性质)。这样,每次转移的时间是 $O(m)$的,转移的次数与学生上车时间的范围有关。
 
但是题目中 $t_i \le 4 \times 10^6$,乘上 $m$ 后太大,不能接受,因此需要找办法压缩上车时间的范围。
 
不难发现,当 $t_i$ 均匀分布在 $0$ ~ $4 \times 10^6$时,$t_i$ 两两间隔远远大于 $2 \times m$。根据刚才发现的性质,同样可以发现当两个 $t_i$ 相距大于 $2\times m$ 时,互相之间对结果并不产生影响,因此可以将所有大于 $2\times m$ 的距离设为 $2\times m$,这样学生上车时间的范围就被压缩到了 $0$ ~ $2 \times n \times m$,总时间复杂度是 $O(n\times m^2)$,是可以被接受的。
 
 
==Problem B==
 
 
原本这题有 $O(n^2 \times logn)$ 的做法,但 $O(n^3)$ 同样能过。
 
考虑确定矩形上下边界的情况,将每一列上在边界内的两种蜡烛分别求和变为一维,可以发现,我们要求的是一段最短的,不含G蜡烛的,含最多H蜡烛的子段,很容易 $O(n)$求解。
 
比较麻烦的是,如果直接 $O(n^3)$ ,很有可能被卡常,因为在这里 $n$ 是 $1000$,但只有 $500$ 个点,因此可以先对点的坐标离散化,在最后计算面积的时候映射回来。
 
 
==Problem C==
 
 
这题看上去数据范围很大,但是做起来其实很容易。
 
不难发现,对于平衡二叉树,我们如果暴力处理每一棵子树,总复杂度是 $O(n\times logn)$ 的,在接受范围之内。
 
但是如果暴力处理每一棵子树,遇到两条链这样的情况,复杂度会随着最大深度飙升。那么,如何处理?
 
其实,只要在每次判断两棵树是否相同时,除了当前节点权值多判断两个值:总子节点数量和子节点权值和,就可以保证在非平衡时 $O(1)$ 返回答案,在平衡时不会比平衡二叉树更差。
 
 
==Problem D==
 
 
对于每一个确定的 $k$,根据题意模拟即可。创造一个优先队列,先把前 $k$ 个$d_k$ 放进去,每次取出最小的一个,加上 $d_i$,再放回去。
 
显然,$k$ 越大,结束时间越早,因此符合二分答案的应用范围,对 $k$ 二分即可。
 
 
==Problem E==
 
 
走三步和走一步其实没有什么区别。
 
令 $dp_{i,j,k}$ 表示第 $k$ 步走到点 ($i,j$)的最快时间,状态转移方程很容易就可以推导出来,除了 $dp
 
_{i,j,k}$ 是 $dp_{i+dx,j+dy,k-1}$ 的最小值之外,如果 $k$ 是 $3$ 的倍数再将 $dp_{i,j,k}$ 加上 $a_{i,j}$ 即可。总步数不会超过 $n^2$,$O(n^4)$ 的复杂度在接受范围之内。
 

Latest revision as of 08:18, 7 March 2019