博客园链接：https://www.cnblogs.com/Macw07
> 序言，这次排位赛绝对是最轻松的一次排位赛了（打了四次排位赛，终于上了白银组别）。肉眼可见 ACGO 的用户量在慢慢地增长（至少参赛人数变多了，是件好事）[狗头]。
>
> PS：在提供 Cpp 标准代码的时候，本文也会同时提供 Python 版本的代码。但 Python 的执行效率不高，同样复杂度的代码 Python 的效率可能是 C++ 代码的十分之一。因此在使用 Python 代码做题的时候，需要时刻注意复杂度和常数，否则有可能出现超时的情况。
第一题 - A23466.捉迷藏
题目链接跳转：A23466.捉迷藏
第一题算是一个签到题，题目要求给定两个数字 A,BA, BA,B 输出在 [0,9][0, 9][0,9] 区间内不是 A×BA \times BA×B 的任意数字。此题非常简单，可以暴力破解，也可以使用玄学算法。
暴力算法很好想，尝试 [0,9][0, 9][0,9] 之间的所有数字即可，找到一个符合标准的结果就输出。
由于我们知道，000 乘上任何数字都为 000，因此对于所有的测试点，只要 A≠0A \neq 0A=0 且 B≠0B \neq 0B=0，那么输出 000 即可（毕竟无论如何答案也都不会是 000）。反之，输出任意一个非零的数字即可。玄学代码如下：
本题的 Python 代码如下（不得不说，用 Python 的代码量确实减少很多）：
两个代码的时间复杂度都是 O(1)O(1)O(1)，但是第二个算法的复杂度可以精确到 Θ(1)\Theta(1)Θ(1)。
第二题 - A23467.最长公共前缀
题目链接跳转：A23467.最长公共前缀
这道题也非常的简单。题目要求求出两个数字的最长公共前缀的长度。例如字符串 interview 和 interrupt 的最长公共前缀就是 inter，所以应该输出 555。
具体地，在遍历的时候判断两个字符串中同一个索引对应的两个字符是否相等，如果相等就将答案长度增加，否则就停止循环就可以了。PS：在遍历的过程中需要注意不要让索引超限。
本题的 AC 代码如下：
本题的 Python 代码如下：
本算法的时间复杂度约为 O(min(lena,lenb))O(\min(\text{lena}, \text{lenb}))O(min(lena,lenb))。其中，lena 与 lenb 分别代表读入进来的两个字符串的长度。
第三题 - A23468.坏掉的数字键
题目链接跳转：A23468.坏掉的数字键
根据题意，我们需要统计在 NNN 个字符串中，有多少个字符串不包括字符 DDD。循环遍历一个一个匹配实在太麻烦了，直接使用 string 类自带的 .find() 函数即可。直接用 Cpp 的内置函数即可（内置函数大法真好用）。
a.find(b) 表示在 a 中寻找 b。如果找到了就返回 b 第一次在 a 中出现的位置，否则就返回 string::npos。
本题的 AC 代码如下：
本题的 Python 代码如下：
本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间复杂度约为 O(n×d)O(n \times d)O(n×d)，其中 d 表示读入进的字符串长度。更进一步地，a.find(b) 函数的时间复杂度为 O(lena×lenb)O(\text{lena} \times \text{lenb})O(lena×lenb)。其中，lena 与 lenb 分别代表两个字符串的长度。对于本道题而言，lenb 的值永远为 111。
第四题 - A23469.奇怪的次方
题目链接跳转：A23469.奇怪的次方
根据题目要求，我们需要找到一个整数 XXX，满足 XN=YX^N = YXN=Y。根据数学的基本运算法则，我们对等式两遍同时开 NNN 次根即可得到 X=YNX = \sqrt[N]{Y}X=NY 。最后判断再校验一边答案即可。需要注意的是，本题涉及关于小数的运算，因此在实现过程中需要使用 double 数据类型，同时也要关注计算机在处理浮点数存在的误差（使用 round 函数可以将一个数字四舍五入）。
本题的 AC 代码如下：
本题的 Python 代码如下：
本算法的时间复杂度约为 O(1)O(1)O(1) 级别。对于 pow 函数的时间复杂度无法被精确地推算，因为在 C++ 底层中该函数会使用多种不同的算法来实现相同的功能，但一般情况是 log2(n)log_2(n)log2 (n) 级别的。
第五题 - A23470.隐藏元素
题目链接跳转：A23470.隐藏元素
先讲一个运算法则 ，如果 Ai⊕Aj=kA_i \oplus A_j = kAi ⊕Aj =k，那么 Ai⊕k=AjA_i \oplus k = A_jAi ⊕k=Aj 。因此，当我们知道了 A1=1A_1 = 1A1 =1 的时候，我们就可以推出所有有关 A1A_1A1 的线索的另一个数字 AjA_jAj 的值。一旦确定了一个数字，就可以确定所有与之有关联的数字（线索）。
为了方便起见，我们可以建立一个无向图，这样子就可以通过类似拓扑排序的方式按照顺序一个一个地推断出剩余的未知数。如果有一条线索 Ai Aj KA_i\ A_j\ KAi Aj K，那么我们就在 AiA_iAi 和 AjA_jAj 直接连接一条无向边，权值为 kkk，最后对这个图从 111 点开始进行拓扑排序就可以了。
需要注意的是，一个点如果已经被访问过的话，就不需要再被访问了，用 vis 数组记录一下就可以了。本题的 AC 代码如下：
本题的 Python 代码如下：
以上算法基于 广度优先搜索/拓扑排序 实现，该算法的时间复杂度约为 O(M)O(M)O(M)。
第六题 - A23471.圣诞礼物
题目链接跳转：A23471.圣诞礼物
一道很明显的完全背包问题，但需要加以优化。如果不优化的话，按照本题的数据量，在极端情况下程序会运行 105×105=101010^5 \times 10^5 = 10^{10}105×105=1010 次，大概需要 222 分钟时间（其实也不是很久）。因此我们需要在原本的完全背包的基础上加以优化：
通过观察可以发现，虽然物品的数量有 10510^5105 种，但是每种物品的花销却极其的少。就算有一个幸运数字为 888888888888888888888888888，那么也只需要 636363 个圣诞糖果就可以。假设有多个幸运数字都需要 101010 个糖果，那按照贪心的思路：如果我们要选支出则 636363 个圣诞糖果的话，我们可以获得的最大收益就是所有需要 101010 个糖果的幸运数字所对应的可以获得的金币数量的最大值。我们可以通过一个数组来记录对于每一种支付的糖果组合，可以获得的最大金币数量。
这样子我们就将原本的物品数量成功压缩成了 636363 种物品，即可通过本题的所有测试点。本题的 AC 代码如下：
本题的 Python 代码如下：
本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间的多项式时间复杂度约为 O(63M)O(63M)O(63M)，经过化简后的复杂度约为 O(M)O(M)O(M)。其中，数字 636363 代表最多存在 636363 中不同的“物品”。
