金牌题/tuu

Sol1 · 2022-07-13 23:21:57 · 个人记录

给定若干字符串 s_1,s_2,\cdots,s_n，判断是否存在一个字符串 T，满足每次从 T 中删去一个 s_i 直到不能删为止，最终能得到两种以上本质不同的字符串。

很有超现实树的感觉，考虑类似的放缩想法。首先考虑去除没有用的字符串。如何判断一个字符串能否被删空？

自然的想法是贪心，能删就删。注意到如果能够用更小的字符串删空，那么它就没有用。如果能删一部分但是不能删空，那么我们可以声称我们找到了一种方式让它卡在一个非空串动不了，而直接删掉整个串可以让它卡在空串。从而我们可以直接返回 Yes。对于完全动不了的情况，这个字符串有用。

考虑有用的字符串集合的性质。容易发现不会有一个串包含另一个串，否则要么更大的没用，要么已经返回 Yes。注意到这个结论的本质是小的那个串可以被删，于是可以略微推广：一个串的任意非空真子串均无法被删空。

尝试简化最终的形态。定义 T 里面的一个删除单元 u 为一个被删去的连续子串，满足这个子串的第一个字符和最后一个字符在同一次操作中被删去。

设 T 的两种得到本质不同最终字符串的删除方案中，删除单元序列一次为 u_1,u_2,\cdots,u_p 和 v_1,v_2,\cdots,v_q。不妨设 u_1 的起点在 v_1 前面。那么出现在 u_1 之前的字符全部可以删去，所以可以将 u_1 视为字符串的一个前缀。

首先，u_1 和 v_1 必须相交，否则可以在 v 里面加入 u_1。

如果 v_1 和 u_2 不交，那么如果 T 到 v_1 末尾的前缀是坏的，我们就得到了一个两种方案都只有一个删除单元的坏字符串。否则我们直接把它拿掉，剩下的必然还是坏的，而且删除单元个数减少了。

如果 v_1 和 u_2 相交：设 v_1 前面的部分是 A，u_1,v_1 相交的部分是 B，v_2 的其余部分是 C。首先如果 B 中存在一个完整的 s，可以直接将它抽出，不产生任何影响。接下来，考虑从 T 中去除 A。由于现在 B 中不存在完整的 s，u_1 将会完全消失。如果现在 T 变成好的，即两种方法得到一样的最终结果，那么由于 u_2 无法到达 B 段，C 段后面将接一段 B 段。而在原来的 T 中，如果 C 段后面接 B 段，那么在删去 v_1 后将存在一个 AB=u_1，因此 v 不合法，矛盾！从而去除 A 不会使得 T 变成好的。而去除 A 以后，u 少一个元素。

所以如此递推，最后一定能删到两种方案中各仅存在一个删除单位。

但是这个结论仍然不尽如人意——删除单元的结构仍然复杂。

首先，两个删除单元不交的地方不能出现完整的 s，否则另一侧的那里就可以去掉这个 s。因此 v 跨过 u 的右端点的部分一定是一个完整的 s。

然后我们考虑把 s 外面的部分全部去掉。设仅 u 的部分是 A，u,v 相交，s 左边的部分是 B，u,v,s 的交是 C，u 右侧，v,s 的交是 D，其余部分是 E。原本有 A\neq D+E。在执行这一操作后，如果 T 变好，那么 A+B=D。那么 D+E=A+B+E，而 B+E=B+C+D+E-s=v-s 可以删去，即删去 u 无法达到终点，矛盾！于是现在 T 依然是坏的。

由于现在 u 侧可能出现完整 s，先将它们全部抽出，显然 T 还是坏的。现在 v 变成一个 s，因此 u 必须是一堆 s 嵌套。重复上面的操作，T 将变成两个 s 单词接龙起来。

于是我们只需要考虑两个 s 单词接龙起来的情况即可。

首先考虑如何贪心删除。把所有串拿出来建 ACAM，用一个栈保存目前经过的点。如果匹配到一个字符串，将那个字符串在栈里面对应的点弹掉，并记录一个删除总长度信息，利用总长度判断是没删/删空/删一半。

然后考虑找单词接龙的串，对每一个有用的串，跳 fail，然后考虑跳到的那个点，如果那个点的 trie 子树里面有两个以上有用串则必然有一个的后面和当前串的前面不一样，返回 Yes。否则可以利用 fail 的祖先关系来 O(1) 判断那个串的后缀和当前串的前缀是否一样。

于是就做完了，O(|\Sigma|\sum s)，本题中 |\Sigma|=4，轻松通过。