ACGO 第9次排位赛题解
写在前面
本次排位赛 EEE 题「隐藏元素」数据已加强。
本次排位赛再次对题目难度进行调整，同时赛后会统计大家的解题情况，以将排位赛的题目难度定在一个合理的档位。
本场排位赛的所有题目的难度评级为：
A B C D E F 捉迷藏 最长公共前缀 坏掉的数字键 奇怪的次方 隐藏元素 圣诞礼物 入门 入门 入门 普及- 普及/提高- 普及/提高-
同时本次比赛作为 Acgo\tt{Acgo}Acgo 平台第一场接入 Python\tt{Python}Python 的比赛，鼓励所有使用 Python\tt{Python}Python 的同学参加，调整了时间限制，并增强数据「强度」。
非常感谢大家参加本场排位赛！
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
直播预告
直播时间：6月22日（周六）16:00 开始
直播地址：B站ACGO官方账号
直播内容：排位赛#9复盘
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题解简述
以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的AC代码包括复杂度分析，请点击题目标题查看。
A - 捉迷藏
我们可以有很多种方法解决这个问题：可以使用循环枚举 [0,9][0,9][0,9] 之间的所有数字，也可以使用分支语句分类讨论，当然也有比较聪明一些的方法。
观察题目不难发现，A×BA \times BA×B 的结果只有 [0,1,2,3,4,6,8,9][0, 1, 2, 3, 4, 6, 8, 9][0,1,2,3,4,6,8,9] 这几种结果，而 555 和 777 这两个数字是无法得到的。所以我们直接输出 555 或者 777 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B - 最长公共前缀
我们可以使用一个变量 iii 从 000 开始依次比较两个字符串的当前字符，直到遇到不相等的字符，或者其中一个字符串遍历完毕停下来，此时 iii 就是两个字符串的最长公共前缀的长度。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C - 坏掉的数字键
对于读入的每个 AiA_iAi 检测其是否含有数字 DDD，有两种方法：1.数位分离判断是否出现 DDD；2. 把 AiA_iAi 当作字符串，在其中查找字符 DDD 是否存在即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D - 奇怪的次方
题目解析
显然 XXX 越大， XNX^NXN 就越大，答案有单调性，所以我们可以使用二分来快速计算 XXX 的值。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E - 隐藏元素
题目解析
本题需要我们根据各个变量 AiA_iAi 和 A1A_1A1 的关系来推出 AiA_iAi 的值。
我们可以根据给出的 MMM 条信息来构建一个无向图：
对于 Ai⊕Aj=kA_i \oplus A_j = kAi ⊕Aj =k，我们可以构建一条 (i,j)(i, j)(i,j) 的边权为 kkk 的边。
最后使用 DFS/BFS\tt{DFS}/\tt{BFS}DFS/BFS 从 111 开始遍历整个图，对于遍历到的每个点 uuu 其所有的邻接点 viv_ivi ，那么 Avi=Au⊕wu→viA_{v_i} = A_u \oplus w_{u \rightarrow v_i}Avi =Au ⊕wu→vi 。
遍历结束以后没有遍历到的点，说明无法判断其和 A1A_1A1 的关系，输出 −1-1−1 即可。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F - 圣诞礼物
如果我们直接忽略数据范围，不难发现可以使用完全背包的DP模型来解决这道问题，定义 dp[i][j]dp[i][j]dp[i][j] 为前 iii 个礼物，使用 jjj 个糖果能够获得的最多金币。
但是注意到本题的数据范围 N,M (1≤N,M≤105)N, M\ (1 \le N, M \le 10^5)N,M (1≤N,M≤105) 如果使用上述递推式，时间复杂度为 O(N×M)\mathrm{O}(N \times M)O(N×M)。会超出本题的时间限制。
那么进一步分析题目我们会发现对于每个礼物 AiA_iAi ，制作出礼物需要的糖果为 f(Ai)f(A_i)f(Ai )，其中 1≤Ai≤1091 \le A_i \le 10^91≤Ai ≤109，我们不难发现，2≤f(Ai)≤632 \le f(A_i) \le 632≤f(Ai )≤63；
而对于每个 f(Ai)f(A_i)f(Ai ) 由于可以重复制作同一种礼物，所以只需要取 maxBi\max{B_i}maxBi 即可。
所以我们可以转换 dp[i][j]dp[i][j]dp[i][j] 定义为制作需要糖果数量不超过 iii 的礼物，使用 jjj 个糖果能够获得的最多金币。
那么此时的时间复杂度转化为 O(K×M)\mathrm{O}(K \times M)O(K×M) 其中 K=63K = 63K=63。
> 使用 Python 的同学请不要使用 min/max 函数，非常耗时，建议改用 if 语句。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
