+++ date = "2020-10-05T16:10:00+08:00" draft = false tags = [] title = "CSP September 2020" authors = ["xry111"] +++ # 第 20 次 CCF 计算机软件能力认证 ## [检测点查询](http://118.190.20.162/view.page?gpid=T113) ### 问题重述 给定一个点集 $S \subset \mathbb{R}^2$,再给定一个点 $p \in \mathbb{R}^2$, 求 $S$ 中到 $p$ 的欧几里德距离最小的三个点。 ### 题解 签到题,随便搞一下就行了。 ## [风险人群筛查](http://118.190.20.162/view.page?gpid=T112) ### 问题重述 给定一个矩形区域 $A \subset \mathbb{R}^2$,再给定若干点列 (点都属于 $\mathbb{R}^2$),问存在一个点属于该矩形区域的点列个数, 和存在两个相邻的点属于该矩形区域的点列个数。 ### 题解 签到题,随便搞一下就行了。 ## [点亮数字人生](http://118.190.20.162/view.page?gpid=T111) ### 问题重述 给你一个组合逻辑电路 (包含与、或、非、异或、与非、或非、异或非门), 保证电路没有反馈环,给定电路的一组输入,求每个逻辑门的输出。 ### 题解 超级大模拟,为了简化实现,我们可以将逻辑门抽象成 ```c++ struct gate { int rev; std::function aggr; }; ``` 这样的东西,这样就能用统一的逻辑处理各个逻辑门了:用函数对象 `aggr` 把输入组合一下,然后异或一下 `rev`,起到反向的效果。 STL 自带的 `std::bit_or`, `std::bit_and`, 以及 `std::bit_xor` 对象可以直接赋给 `aggr`。 现场比赛的时候忘了异或 `rev`,居然能过样例,结果交上去 $0$ 分自闭了很久…… 然后就拓扑排序一下,逆序求每个逻辑门的输出就行了。 ## [星际旅行](http://118.190.20.162/view.page?gpid=T110) ### 问题重述 给你个高维球 $B \subset \mathbb{R}^n$, 以及 $m$ 个点 $p_i \in \mathbb{R}^n$, 对于每个点,求出它到其余所有点的,不经过高维球内部的最短路径的长度之和。 ### 题解 这题有 $70\\%$ 的数据是 $3$ 维以下,就是 [2018 EC Final 原题](https://codeforces.com/gym/102056/problem/F), 我当时在赛场上就不会,后来退役了就懒得补题 (导致这次丢掉了校 rk 1) (rk 1 说他改一个小地方这题就能 95 分,[点击这里可以 orz 他][fc])。 比赛的时候发现是高维, 就考虑先解决 $2$ 维,然后找到正确的平面投影上去做, 结果 $2$ 维的都做了两个半小时:一开始只看到结果是 WA,以为精度爆炸了, 最后才发现可以看每个点的评测结果,发现都是 RE,惊觉 $n$ 和 $m$ 的范围看反了……改对以后比赛就剩 $10$ 分钟了,只拿了 $35$ 分。 [fc]: https://www.cnblogs.com/flukehn/p/13689341.html 其实就算能迅速解决 $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 整数溢出相关内建函数][gcc-builtin-overflow],只好手动判断)。 [gcc-builtin-overflow]: https://gcc.gnu.org/onlinedocs/gcc-10.2.0/gcc/Integer-Overflow-Builtins.html 然后还有一种直线经过球,但是线段不经过球的情况, 此时 $\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$,从而通过本题。 ## [密信与计数](http://118.190.20.162/submitlist.page?gpid=T109) ### 问题重述 给你一个根据密文解出明文的 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$ 真的离谱……