Difference between revisions of "2019 ECNU XCPC March Selection"

@@ 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)$ 的复杂度在接受范围之内。

Difference between revisions of "2019 ECNU XCPC March Selection"

Latest revision as of 08:18, 7 March 2019

Navigation menu

Search