CSP September 2020

第 20 次 CCF 计算机软件能力认证

检测点查询

问题重述

给定一个点集 $S \subset \mathbb{R}^2$,再给定一个点 $p \in \mathbb{R}^2$, 求 $S$ 中到 $p$ 的欧几里德距离最小的三个点。

题解

签到题,随便搞一下就行了。

风险人群筛查

问题重述

给定一个矩形区域 $A \subset \mathbb{R}^2$,再给定若干点列 (点都属于 $\mathbb{R}^2$),问存在一个点属于该矩形区域的点列个数, 和存在两个相邻的点属于该矩形区域的点列个数。

题解

签到题,随便搞一下就行了。

点亮数字人生

问题重述

给你一个组合逻辑电路 (包含与、或、非、异或、与非、或非、异或非门), 保证电路没有反馈环,给定电路的一组输入,求每个逻辑门的输出。

题解

超级大模拟,为了简化实现,我们可以将逻辑门抽象成

struct gate
{
	int rev;
	std::function<int(int, int)> aggr;
};

这样的东西,这样就能用统一的逻辑处理各个逻辑门了:用函数对象 aggr 把输入组合一下,然后异或一下 rev,起到反向的效果。 STL 自带的 std::bit_or<int>, std::bit_and<int>, 以及 std::bit_xor<int> 对象可以直接赋给 aggr

现场比赛的时候忘了异或 rev,居然能过样例,结果交上去 $0$ 分自闭了很久……

然后就拓扑排序一下,逆序求每个逻辑门的输出就行了。

星际旅行

问题重述

给你个高维球 $B \subset \mathbb{R}^n$, 以及 $m$ 个点 $p_i \in \mathbb{R}^n$, 对于每个点,求出它到其余所有点的,不经过高维球内部的最短路径的长度之和。

题解

这题有 $70\%$ 的数据是 $3$ 维以下,就是 2018 EC Final 原题, 我当时在赛场上就不会,后来退役了就懒得补题 (导致这次丢掉了校 rk 1) (rk 1 说他改一个小地方这题就能 95 分,点击这里可以 orz 他)。 比赛的时候发现是高维, 就考虑先解决 $2$ 维,然后找到正确的平面投影上去做, 结果 $2$ 维的都做了两个半小时:一开始只看到结果是 WA,以为精度爆炸了, 最后才发现可以看每个点的评测结果,发现都是 RE,惊觉 $n$ 和 $m$ 的范围看反了……改对以后比赛就剩 $10$ 分钟了,只拿了 $35$ 分。

其实就算能迅速解决 $2$ 维,那个投影估计也会精度爆炸或者超时……

赛后 dalao 们说这个题可以用只需要求点积和距离的方法,这样做多少维都一样。 我们以球心为原点建立坐标系,就是把输入的坐标都减掉球心 $O$ 的坐标, 就不用考虑球的位置了。首先判断从 $A$ 沿直线走到 $B$ 是否不经过球, 先判断直线是否与球相交,就要求直线 $AB$ 到球心的距离。 我们先把 $OB$ 投影到 $AB$ 方向,然后从 $OB$ 中去掉这个投影分量, 就得到 $OB$ 垂直于 $AB$ 的分量,其长度就是 $AB$ 到 $O$ 的距离。 写成公式就是

$$d^2 = |OB|^2 - (\frac{\vec{OB} \cdot \vec{AB}}{|AB|})^2$$

直线不经过球内部就是 $d^2 \geq r^2$,代入上面 $d^2$ 的公式, 移项,得到

$$|AB|^2(|OB|^2 - r^2) \geq (\vec{OB} \cdot \vec{AB})^2$$

这个式子的一个问题是左边可能超过 $64$ 位整数的表示范围, 如果拿 Python 写肯定会超时 (这题常数卡得很死) __int128 的话不知道评测机资不资瓷。 幸运的是右边根据数据范围判断也就 $10^{16}$ 数量级, 所以我们可以判断一下,如果左边运算会溢出,可以直接认为不等式成立 (垃圾评测机不支持 __builtin_smulll_overflow 之类的 GCC 整数溢出相关内建函数,只好手动判断)。

然后还有一种直线经过球,但是线段不经过球的情况, 此时 $\angle BAO$ 和 $\angle ABO$ 必有一个是钝角。 根据余弦定理,这就相当于

$$\vec{AB} \cdot \vec{AO} < 0$$

$$\vec{BA} \cdot \vec{BO} < 0$$

对于上面这些线段不经过球的情况,$|AB|$ 就是距离。对于剩下的情况, 我们需要在球上做一个弧 $PQ$,使之与 $AP$ 和 $QB$ 都相切。 根据勾股定理,以及切线的性质,很容易求出

$$|AP|^2 = |OA|^2 - r^2$$ $$|QB|^2 = |OB|^2 - r^2$$

开方即可算出路径中的两段直线长度。 剩下的问题就是求出 $PQ$ 的弧长,它就是 $r \cdot \angle{POQ}$。 首先求 $\angle{AOB}$,根据余弦定理它就是

$$cos^{-1} \left( \frac{\vec{OA} \cdot \vec{OB}}{|OA| \cdot |OB|} \right)$$

然后求出 $\angle{AOP}$,它显然是

$$cos^{-1} \left( \frac{r}{|OA|} \right)$$

同理可求出 $\angle{BOQ}$:

$$cos^{-1} \left( \frac{r}{|OB|} \right)$$

即可求出 $\angle{POQ}$:

$$\angle{POQ} = \angle{AOB} - \angle{AOP} - \angle{BOQ}$$

直接用上面这些公式暴力做会超时,因为点积的次数太多了 (我随便写了一下是 $5m^2$ 次),而本题毒瘤卡常 (补题用的评测姬还比现场赛时候烂)。 注意到在对点 $A$ 和 $B$ 算答案时,涉及的向量都是 $\vec{OA}$ 与 $\vec{OB}$ 的线性组合。根据点积的性质,我们可以将这些向量的点积写成 $\vec{OA} \cdot \vec{OA}$、$\vec{OB} \cdot \vec{OB}$、$\vec{OA} \cdot \vec{OB}$ 的线性组合。这样我们预处理 $m(m-1) / 2 + m$ 个点积出来就行了, 即可将点积的次数减少到原来的 $1/10$,从而通过本题。

密信与计数

问题重述

给你一个根据密文解出明文的 DFA,保证密文和明文是一一对应的。 再给定一个词典,用词典中的单词拼成长度为 $m$ 的明文,要求明文加密后, 对应的密文中不出现词典中的任何单词。求方案数。

DFA 状态数 $n$ 不超过 $50$,$m$ 不超过 $1000$, 单词长度之和 $w$ 不超过 $50$。

题解

因为密文和明文是一一对应的,我们可以搞出将明文加密成密文的 DFA。 考虑“密文不出现词典中任何单词”的条件,这就相当于把词典搞成一个 Aho-Corasick 自动机,然后拿密文在上面跑,单词末尾的那些状态是禁入的。 用 $f(m, a, b)$ 表示长度为 $m$,加密 DFA 状态为 $a$,A-C 自动机状态为 $b$ 的方案数,再预处理一下每个单词会导致状态从 $(a, b)$ 变到哪里, 然后暴力转移递推即可。时间复杂度是 $\mathcal{O}(m n w^2)$。

为啥现场赛交带 freopen 的程序居然能过啊?

$10^8$ 复杂度跑 $93ms$ 真的离谱……

Xi Ruoyao
Xi Ruoyao
PhD Student

Retired from ICPC, now a PhD student and an assistant ICPC coach (with no salary).