[蓝桥杯 2026 国 A] 魔法前缀 - 题目

内存限制：512 MiB 时间限制：2000 ms 标准输入输出

题目类型：VJudge（洛谷）评测方式：VJudge

上传者：匿名

提交提交记录统计讨论题解

小蓝和小桥共同维护一个大型词库。为了清理存储空间，他们决定通过一个“前缀修剪”的魔法游戏来删除不必要的单词前缀。

词库中包含个由小写英文字母构成的单词。

定义词库的有效前缀集合为：词库中所有单词的全部非空前缀构成的集合。相同前缀只保留一次。例如，如果词库中只有单词 cat 和 car，那么有效前缀集合为 c、ca、cat、car。

游戏规则如下：

小蓝和小桥轮流操作，小蓝先手；
每次操作时，当前玩家必须从当前有效前缀集合中选择一个非空前缀；
选择后，当前集合中所有以为前缀的字符串都会被删除，包括本身。举个例子：若当前有效前缀集合为 "a", "ap", "app", "b", "ba"，如果玩家选择了 "ap"，那么 "ap" 和 "app" 都会被删除，集合将变为 "a", "b", "ba"。
当轮到某名玩家时，如果有效前缀集合为空，则该玩家输掉游戏。

两人都会采取最优策略。现在给定初始词库，请你判断最终谁会获胜。

第一行包含一个整数 , 表示测试用例组数。

对于每组测试用例：

第一行包含一个整数 , 表示词库中的单词数量。

接下来行，每行包含一个由小写英文字母构成的字符串，表示一个单词。

对于每组测试用例，输出一行。若小蓝必胜，输出 XiaoLan；否则输出 XiaoQiao。

2
2
ab
cd
2
cat
car

XiaoQiao
XiaoLan

第一组样例中，有效前缀集合为 a、ab、c、cd。两个分支结构完全相同。无论小蓝选择其中一个分支上的哪个前缀，小桥都可以在另一个分支上作对称操作，因此小桥必胜。

第二组样例中，有效前缀集合为 c、ca、cat、car。小蓝第一步选择 c，即可删除整个集合，使小桥无可操作，因此小蓝必胜。

对于的评测用例，单组测试用例中所有字符串总长度不超过。

对于所有评测用例，, 。单个测试文件中所有测试用例的字符串总长度之和不超过。所有字符串均仅包含小写英文字母。

编辑器加载中 …

或者，上传代码文件

Powered by SYZOJ. Modified by Zemu (UnratedCheater).

当前版本：V1.7.2-premium

#216789. [蓝桥杯 2026 国 A] 魔法前缀