题解：P9218 「TAOI-1」Apollo

LionBlaze · 2025-10-05 19:47:55 · 题解

如果你看懂了题目，你会发现 f(a) 其实就代表 a 的小数位数。

而 g(x,y) 怎么求呢？

显然，如果 x 或 y 之间有整数，也就是它们的整数部分不同。如果整数部分相同，那么如果第一位小数不同，则答案为 1。如果整数和第一位小数都相同，但是第二位小数不同，则答案为 2，以此类推。

但是上面的讨论是有问题的：实际上，如果 x 或 y 的某一位小数相同（前面也相同），但是某个数字后面没有小数位了，则由于区间是闭区间所以包括 x 和 y，答案就是 f(x) 或 f(y)，但是根据上述讨论需要继续往后看直到 y 的某一位不为 0。做法也很简单，因为要满足这样的条件必须 x 或 y 转化为字符串后一个是另一个的前缀。

等等，前缀？我们在讨论数学为什么要看这个。实际上，如果把 x,y 都转化为字符串并令两个字符串的最后一个字符不和任何字符相同，则 g 函数值就是：

• 它们整数部分不同：0。
• 否则：它们的第一个不同的位置。

::anti-ai[我草我怎么写得这么像 AI，坏了。]

如何把这个讨厌的整数部分的检测去掉呢？非常简单，因为贡献是 0 所以可以不算，事先对所有数字分组，整数部分相同的分到同一组，组内统计即可。组间答案是 0 的。

那么，假设整数部分相同，如何统计答案呢？

这就是一个串串题了。Trie 树板子题，建出 Trie 树后求一个节点和其它所有节点的 LCA 深度之和。在每个节点上标记子树中有多少个字符串即可。