「POI2009 R1」算法加速 Algorithm Speedup 题解

问题分析

我们需要计算一个递归定义的函数 $\mathbf{F}(x, y)$，其中：

• $\mathbf{W}(x)$ 是序列 $x$ 中所有不同元素组成的集合
• $\mathbf{p}(x)$ 是 $x$ 的最长前缀，且 $\mathbf{W}(\mathbf{p}(x)) \neq \mathbf{W}(x)$
• $\mathbf{s}(x)$ 是 $x$ 的最长后缀，且 $\mathbf{W}(\mathbf{s}(x)) \neq \mathbf{W}(x)$

函数定义：

1. 如果 $\mathbf{W}(x) \neq \mathbf{W}(y)$，返回 $0$
2. 如果两个集合都只有一个元素，返回 $1$
3. 否则返回 $\mathbf{F}(\mathbf{p}(x), \mathbf{p}(y)) \wedge \mathbf{F}(\mathbf{s}(x), \mathbf{s}(y))$

关键观察

1. $\mathbf{p}(x)$ 和 $\mathbf{s}(x)$ 的含义

$\mathbf{p}(x)$ 是去掉序列末尾的一些元素，使得集合大小减少的最长前缀。
$\mathbf{s}(x)$ 是去掉序列开头的一些元素，使得集合大小减少的最长后缀。

实际上：

• $\mathbf{p}(x)$ 是去掉使得集合完整的最后一个元素之前的部分
• $\mathbf{s}(x)$ 是去掉使得集合完整的第一个元素之后的部分

2. 递归性质

每次递归调用时，集合的大小都会减少至少 $1$。
由于值域只有 $1$ 到 $100$，递归深度最多为 $100$。

3. 问题转化

这个函数实际上在检查两个序列是否在某种"压缩表示"下相同。
可以理解为：两个序列的"骨架结构"是否相同。

高效解法

1. 预处理集合信息

对于每个序列，我们可以预处理：

• 整个序列的元素集合 $\mathbf{W}(x)$
• 所有前缀的集合变化点
• 所有后缀的集合变化点

2. 快速计算 $\mathbf{p}(x)$ 和 $\mathbf{s}(x)$

使用双指针技术：

• 对于 $\mathbf{p}(x)$：从右向左扫描，找到第一个使得集合变小的位置
• 对于 $\mathbf{s}(x)$：从左向右扫描，找到第一个使得集合变小的位置

具体来说：

• $\mathbf{p}(x)$ 是序列 $x$ 去掉最后一个首次出现的元素之后的前缀
• $\mathbf{s}(x)$ 是序列 $x$ 去掉第一个首次出现的元素之后的后缀

3. 记忆化搜索

由于递归深度有限且序列可能重复出现，使用记忆化存储已计算的结果。
键值可以用序列的起始和结束位置表示。

4. 位运算优化

由于值域只有 $1$ 到 $100$，可以用 64 位整数（或两个 64 位整数）的位掩码表示集合，
这样可以 $O(1)$ 时间比较集合是否相等。

算法步骤

1. 预处理阶段：

   • 对每个序列，计算每个位置的前缀集合和后缀集合
   • 记录 $\mathbf{p}(x)$ 和 $\mathbf{s}(x)$ 的划分点

2. 递归计算：

   • 如果 $\mathbf{W}(x) \neq \mathbf{W}(y)$，返回 $0$
   • 如果 $|\mathbf{W}(x)| = 1$，返回 $1$（因为此时 $|\mathbf{W}(y)|$ 也必须为 $1$）
   • 否则递归计算：

     return F(p(x), p(y)) && F(s(x), s(y))
     

3. 优化措施：

   • 使用记忆化避免重复计算
   • 在递归前先检查简单情况
   • 使用迭代代替深层递归防止栈溢出

复杂度分析

• 预处理：$O(n + m)$ 每个测试用例
• 递归计算：由于集合大小最多为 $100$，递归深度最多 $100$，且每个节点最多有两个子节点，
  但通过记忆化，实际计算的状态数是 $O(\min(n, m) \times \text{集合大小})$ 级别的
• 总体复杂度：对于 $k \leq 13$ 且 $n, m \leq 100000$ 是可接受的

样例分析

样例1

x = [3, 1, 2, 1], y = [1, 3, 1, 2, 1]
W(x) = {1, 2, 3}, W(y) = {1, 2, 3}
p(x) = [3, 1, 2], p(y) = [1, 3, 1, 2]
s(x) = [1, 2, 1], s(y) = [3, 1, 2, 1]

递归计算后发现最终返回 0

样例2

x = [1, 1, 2, 1, 2, 1, 3], y = [1, 1, 2, 1, 3, 1, 3]
W(x) = {1, 2, 3}, W(y) = {1, 2, 3}
经过递归计算后返回 1

总结

本题的关键在于理解递归过程的本质，并通过预处理和记忆化来优化计算。
由于值域有限，我们可以利用位运算等技巧来加速集合操作。
递归深度有限保证了算法在合理时间内完成。