+++
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<int(int, int)> aggr;
};
```

这样的东西，这样就能用统一的逻辑处理各个逻辑门了：用函数对象 `aggr`
把输入组合一下，然后异或一下 `rev`，起到反向的效果。
STL 自带的 `std::bit_or<int>`, `std::bit_and<int>`, 以及 `std::bit_xor<int>`
对象可以直接赋给 `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)，
我当时在赛场上就不会，后来退役了就懒得补题
<del>(导致这次丢掉了校 rk 1)</del>
(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 写肯定会超时 (这题常数卡得很死)
<del>，`__int128` 的话不知道评测机资不资瓷</del>。
幸运的是右边根据数据范围判断也就 $10^{16}$ 数量级，
所以我们可以判断一下，如果左边运算会溢出，可以直接认为不等式成立
(<del>垃圾</del>评测机不支持 `__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)$。

<del>为啥现场赛交带 `freopen` 的程序居然能过啊？</del>

<del>$10^8$ 复杂度跑 $93ms$ 真的离谱……</del>