题解：P11759 [COTS 2014] 基因转换 / GTA

zrl123456 · 2025-11-17 23:11:51 · 题解

:::::info[闲话]{open} 一个魔怔做法。
LCA Project 怎么只开 2s，把我的神秘复杂度做法卡掉了，生气了。
还有就是调题调爽了。
::::: :::::info[题目基本信息] 考察：搜索（暂无难度）。
题目简介：
给定 n 个字符串 \{s_n\}，只由 A、C、G、T 组成，对于所有 i,j\in[1,n] 询问 s_i 能否变换为 s_j，变换规则为：

• 选择一个子串 A，将其替换为 TC。
• 选择一个子串 C，将其替换为 AG。
• 选择一个子串 G，将其替换为 CT。
• 选择一个子串 T，将其替换为 GA。
• 上面所有操作的逆操作。

数据范围：

• 1\le n\le 100
• \forall i\in[1,n],1\le |s_i|\le 5\times 10^4

  ::::: 注意到操作可逆，所以变换具有传递性和交换律，那么最终可以互相变换的会是一个大等价类内的元素。
  考虑将一个字符串串长最小的字符串作为一个等价类的代表，那么我们注意到一个定理：

• 若没有串长为 L（L>1）的字符串作为等价类代表，那么也没有 L+1 的字符串作为等价类代表。 :::::success[证明] 考虑反证法，假设存在 L+1 的字符串作为等价类代表。
  若串长为 L 的字符串没有被作为代表，那么他最终被转化为了串长更小的字符串，那么我们将 L+1 的字符串的一个串长为 L 的子串转化掉就能得到一个串长更小的字符串，与条件矛盾，证毕。
  ::::: 由上述我们还可知，从串长为一个 L 开始后面的字符串都不会存在字符串作为等价类的代表，打表可知串长最长的等价类代表串长为 4。
  那么我们考虑爆搜观察，从所有串长不超过 4 的字符串开始选择一个字符扩展为两个字符，打出表后我们发现扩展到所有长度 10 的字符串后任意一个长度不超过 5 的字符串都存在一个长度不超过 10 的能被其扩展到（别问怎么发现的，多试试就试出来了），所以我们考虑预处理时先从所有串长不超过 4 的字符串开始扩展到所有长度不超过 10 的字符串，然后对于每个 s_i 一个一个字符累加，每当串长不小于 5 那么就爆搜到能被长度不超过 4 的字符串扩展到的长度不超过 10 的字符串（这个需要记忆化），然后将其整体替换为这个长度不超过 4 的字符串，然后它们都被转化为串长不超过 4 的字符串，然后通过 map 和并查集等数据结构一通维护串长不超过 4 的字符串的变换，然后你就暴力地魔怔地很慢地占用空间很大地代码也很长很难调地解决了这道题。

时空复杂度不想分析，就算分析出来了也跑不满。

提交记录（展示运行速度）
code