物理

信息竞赛中的一些算法：深度优先搜索、字典序和“自动高精度”

这是一个关于信息竞赛的帖子。

$A\to B$ 表示把 $A$ 的值设为 $B$。

$a[i]$ 表示数组 $a$ 的第 $i$ 项。

$i$ 除非特殊说明，不指虚数单位。

某些词语可能使用不规范，请大家指出。

$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$

张阿姨说：我的孩子说要学“深度优先搜索”，怎么能依赖于搜索呢？有问题应该自己解决。

赵先生说：我孩子要学“深度优先搜索”，这东西一看就很深奥，怎么能让初中生学呢？

孙女士说：我孩子最近在做什么“高精度”的题，怎么能让孩子算精度要求怎么高的东西呢？算错了怎么办？

－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

$\Huge{\text{一：深度优先搜索}}$

下图是一个树，如何遍历每个节点呢？

[图一]

可以按照图片中数字顺序。

这就是深度优先搜索的顺序。

题目：已知一些数 $a_1\lt a_2\lt\dots\lt a_n$。

已知 $s$，如果 $\sum_{j=1}^ma_{i_j}=s$，求 $i_j$。

如果有多种可能，输出字典序最小的可能。

如果不可能，输出 $\texttt{impossible is nothing}$。

为了防止骗分，有 $N$ 组数据。

深度优先搜索与$\sout{地柜}$递归有异曲同工之妙，深度优先搜索同样也是把复杂的问题拆分成小问题。

比如我们选择了 $1$ 号节点，我们接下来就要搜索 $2$ 号节点和 $3$ 号节点的子节点。

例如这道题，我们可能会选择尝试 $\frac{s}{a_1}$ 能不能这么分解。当然也有可能不能，如果不能，就尝试 $\frac{s}{a_2}$，一直到成功为止。

当我们尝试 $\frac{s}{a_1}$ 能不能这么分解时，应该尝试 $\frac{s}{a_1^2}$ 能不能这么分解、$\frac{s}{a_1a_2}$ 能不能这么分解……直到成功。

当我们尝试 $\frac{s}{a_{c_1}a_{c_2}\dots a_{c_m}}$ 能不能这么分解时，应该尝试 $\frac{s}{a_{c_1}a_{c_2}\dots a_{c_m}a_1}$、$\frac{s}{a_{c_1}a_{c_2}\dots a_{c_m}a_2}$、……、$\frac{s}{a_{c_1}a_{c_2}\dots a_{c_n}a_n}$ 能不能分解。

当然，如果中间某一次尝试成功了，接下来就不必再试了，否则会 TLE。

代码会放在评论区。

$\Huge{\text{二：字典序}}$

顾名思义，就是字典中的顺序。

对于两个排列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_m$ 且 $n\ge m$，

如果 $a_1\gt b_1$，则 $a$ 的字典序更大；如果 $a_1\lt b_1$，则 $b$ 的字典序更大。

如果 $a_1=b_1$，且 $a_2\gt b_2$，则 $a$ 的字典序更大；如果 $a_2\lt b_2$，则 $b$ 的字典序更大。

如果 $a_1=b_1,a_2=b_2$，且 $a_3\gt b_3$，则 $a$ 的字典序更大；如果 $a_3\lt b_3$，则 $b$ 的字典序更大。

……

如果 $\forall i\in\mathbb{N^+},i\ge m,a_i=b_i$，则 $a$ 的字典序更大。

$\Huge{\text{三：“自动高精度”}}$

大家知道，蟒蛇语言（Python）默认的整数类型就是高精度。所以如果有高精度题目，可以直接用它做。

大家也知道，蟒蛇语言的运行速度很慢。面对这种情况，有两种解决方案。

第一种是改用爪哇语言（Java），它也有高精度类型。

第二种是换一个解释器。人们看到它运行速度这么慢，于是又做了一些更快的解释器。

例如 Pypy（可以在洛谷上用）、Cython 等。