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$,但是如果正方形都卡到矩形的边缘,则不需要乘。