第 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$ 真的离谱……