2020.11.12笔记
2020.11.12笔记
CSP.ACCSP-S2周末刷题班(第三场)
A
需要写高精度乘和高精加。
暴力枚举怎么改。
无解的情况有以下几种:
- 前导零,判断的条件是符号或者空白+0+符号或者空白
- 两个符号相邻。
- 符号在开头或者结尾。
B
非常重要的观察是对报废的机器使用魔法棒一定不优。
那么整个过程会变成一个二叉树的结构,每条边的长度为 $m$。
问题变成了选择 $n$ 个叶子,最小化 $\max { dep_i \times m + t_i }$
假设知道了已经选了哪些结点,那么贪心的想法是耗时长的任务应该放在深度浅的叶子上。
这也就意味着连续的一段叶子对应着排序之后编号连续的一段区间。
因此可以设 $f_{l, r}$ 表示编号在 $[l, r]$ 的任务都放好的最小代价,转移的时候枚举断点即可,复杂度为 $O(n^3)$。
实际上不需要 $dp$,可以直接使用和合并果子一模一样的贪心,无脑使用堆可以做到 $O(n \log n)$,实际上新合并出来的值是单调不降的,因此可以直接新开一个队列,复杂度可以做到 $O(n)$。
C
根据套路,首先考虑期望的线性性,那么只要求出每个数出现的概率,再乘上权值即为期望。
设当前询问的区间是 $[l, r]$,则对于编号 $i \in [l, r]$,其出现的概率为:
$$b_i = p_i\prod_{j=i+1}^r(1-\frac{p_j}{m})$$
使用线段树维护区间的答案,$b_i$的和,以及 $(1-\frac{p_i}{m})$ 的乘积即可支持区间查询和区间加权值。
D
非常直观地想法是使用斜率最接近的两个点对应的向量,但是有些点是不优的。
不优的原因是因为这些点不在凸包上,因此求个上凸壳,然后使用夹住 $(x, y)$ 的两个向量进行求解。
再来考虑使用两个向量 $(x_1, y_1), (x_2, y_2)$ 如何计算最小步数。
二分答案 $k$,则 $(kx_1, ky_1), (kx_2, ky_2)$ 会组成一个三角形,若 $(x, y)$ 在三角形内部,则说明可行。
CF17E
正难则反,考虑计算不相交的个数。
使用马拉车求出每个回文中心的最大半径,再使用差分可以求出对于每个点 $i$ ,有多少左端点和右端点在这里,先记为 $l_i, r_i$。
设 $cnt$ 为回文串个数,则答案为:
$$\binom{cnt}{2} - \sum_{i=1}^{n-1}{r_i\sum_{j=i + 1}^nl_j}$$
可以发现最内层不需要枚举,直接后缀和即可。
CF85E
二分答案 $k$ ,然后限制相当于要求距离大于 $k$ 的点对不能在相同的集合里。
检查是否合法就是判断是否为二分图。
记连通块个数为 $cnt$,则答案为 $2^{cnt}$。
这个做法的复杂度为 $O(n^2 \log n)$。
实际上有线性的做法:
首先旋转坐标系,曼哈顿距离转为切比雪夫距离。
问题就变成了使用两个边长相等的正方形覆盖所有点。
假设现在求出所有点的上下左右四个边界构成的矩形,则这两个正方形一定卡到至少一个顶点。
因此可以枚举两个正方形卡到哪个顶点,然后对于所有点,可以根据到顶点的切比雪夫距离,求出应该划分到哪个正方形。
再来考虑如何计算方案数。
对于两个正方形的公共部分里的点,划分到两边都可以,若点数为 $c$,则方案数为 $2^{c+1}$。
有一个细节是如果两种方案求出的 $ans$ 一样,则答案要乘以 $2$,但是如果正方形都卡到矩形的边缘,则不需要乘。