0%

题解 08

暑假快结束了。

2021 杭电多校 07 1004 Link with Balls

$2n$ 个盒子,编号从 1 开始,从第 $2x - 1$ 个盒子可以拿 $kx$ 个球;从第 $2x$ 个盒子可以拿至多 $x$ 个球。$k$ 是非负整数。求一共拿到 $m$ 个球的方法数,答案对 $10^9 + 7$ 取模。
$1 \le T\le 10^5, 1\le n, m\le 10^6$

组合数学题。

看到 $2n$ 一般想到两两配对,然后发现拿 $kx$ 个球的盒子和至多拿 $x - 1$ 个球的盒子可以组合出任意数量的球,而且数量和取法一一对应,那么就是 $n$ 个能拿任意个球的盒子和 $1$ 个能拿 $[0, n]$ 的盒子中取出一共 $m$ 个。

枚举从 $[0, n]$ 盒子中拿出的数量,对于剩下的用插板法分开,添加 $n - 1$ 个位置表示板子之间为空,得到 $\sum_{i = 0}^{n}C_{m - i + n - 1}^{n - 1}$,这个式子直接算会超时,用组合数公式化简成 $C_{m + n}^{m} - C_{m - 1}^{n}$。预处理组合数即可。

2021 杭电多校 07 1005 Link with EQ

一排一共 $n$ 个座位,每个人会选择自己的座位,使自己到已经坐下的所有人最小距离尽量大。有多个可选座位时随机选一个,第一个人会随机选座。当最小距离最大是 $1$ 时,认为这排座位已满。给定座位数量,求座位“已满”时座位上总人数的期望值,对 $10^9 + 7$ 取模。
$1\le T\le 10^5, 1\le n\le 10^6$

概率 dp,主要想清楚子情况的分类。

令两端有人时,$n$ 个空座位的期望人数是 $f(n)$,一端有人时的期望是 $g(n)$,那么它们的递推公式:

以上两个式子,代入情景就能推出来。接下来计算答案。

对于第一个来的人,有 $n$ 个等可能的选择,遍历求和即可,但是同样会超时。记答案为 $h(n)$ 优化一下式子:

维护一下前缀和就好了。

2021 杭电多校 07 1006 Link with Grenade

随机向一个方向以速度 $v$ 投掷一颗起爆时间 $t$,杀伤半径 $r$ 的手雷。手雷从被投出的那一刻开始倒计时,求投掷点不被炸到的概率,对 $10^9 + 7$ 取模。
三维空间,假设手雷不会触地,加速度 $10m/s^2$。
$1\le T\le 10^5, 1\le t, v, r\le 100, t, v, r 是整数$

计算几何题。一开始用随机取弧度去算,一直化不出有理数。后来一查,发现因为面积元的问题,随机弧度获得的点在单位球表面并不是均匀的,我原来的式子还要积出面积。至于证明,是高数下的内容我当然忘光了

不会炸到的投掷方向,形成的是一个向下的球冠,算出它与整个球面的面积比即可。

题解的模型是,把重力加速度反向给投掷点,分开计算投掷点到手雷的距离,得到一个三角形,三边长都已知。可以求出投掷点和手雷位移夹角的三角函数,这个夹角增大时扫过的那块球冠就是安全的部分,诱导公式换一下方向就能算出来。

如果用我一开始的模型,设速度的水平仰角是 $\theta$,分解速度之后算出让投掷点恰好在爆炸边界的仰角(的正弦),这个仰角把球面分成了两个球冠,求仰角减小时扫过的球冠面积。注意这里的加速度和上一个模型反向,化简比较两个结果的时候有点头疼。

两个模型其实只是变换一下坐标系的区别。

2021 杭电多校 07 1009 Smzzl with Safe Zone

平面内,一大一小两个凸包,小凸包是大凸包的子集。小凸包有 $m$ 个顶点,大凸包有 $n$ 个顶点。
定义一点到一个凸包的距离为该点到凸包所有边线段距离的最小值,求大凸包上任一点到小凸包的最远距离,输出距离的平方,对 $10^9 + 7$ 取模。
$1\le T \le 10^4, 3\le m, n\le 10^5, |x|, |y| \le 10^7, \sum m, \sum n\le 10^6, 顶点按逆时针顺序给出$

显然是计算几何。

首先,不需要考虑大凸包上的各个点,只要考虑顶点即可:如果点在的边和最近的边不平行,显然是端点距离最小;如果平行,可以移动到边的端点。

然后是旋转卡壳的一个性质(?)。假设我们有这个顶点以及它最近的边,逆时针枚举下一个顶点,最近的边一定也在逆时针方向,注意不一定是相邻的边。而凸包外一个顶点到各边的距离,按时针顺序排下来长得像二次函数,那么可以用双指针的方法去找最近的边,而不是对于每个顶点都枚举所有边。

最后一定要注意的一点:这题的数据范围允许 double,但是不允许 long long 的平方直接计算距离,比较长度的时候需要用 double,更新答案的时候用对应的 long long 取模。存在丢失精度的问题,但是这题好像不影响。计算几何的题目代码很长,别敲错了。

2021 杭电多校 07 1012 Yiwen with Sqc

给定一个小写字母串 $s$,求所有字符在所有子串中出现次数的平方和,答案对 $998244353$ 取模。
$1\le T\le 100, |s|\le 10^5, \sum |s|\le 5\times 10^6$

字符串 + 加法卷积(忘记了的词)。就目前接触到的字符串题目,做法其实比其他类型杂乱。

显然把各种字符分开记录。当场看出了每个字符的贡献应该用差分相关的东西去做,然后推了半天推不出来。赛后看题解用了二次差分,感觉不太能想到。

推式子的话可以这样做,对于一种字符,记 $s[1, n]$ 是它在各个前缀里出现的次数,有:

这样维护一下前缀就可以超时了。对于每个字符提取出来的离散位置,计算出每段的长度,也可以完成。考虑在头加一个 0 统一下标,末尾加一个 n + 1 简化循环。

注意溢出。