[ABC302C] Almost Equal 题解

chlchl · 2023-05-22 20:52:24 · 题解

Upddate on 2023.8.10：被 hack，改进做法。

提供一个复杂度更优的解法。

题意

给定 n 个长度为 m 的字符串。问是否能将它们重排，使得对于 1\leq i<n，将第 i 个字符串恰好更改一个字符后可以变成第 i+1 个字符串。

Solution

由于 n,m 极小，我们可以每两个匹配一次，然后看看它们是不是恰好差一个字符，如果是就打上标记。

接着我们从图论的角度去看，那这样的话打上的标记都是双向边。如果度为 2 的点不超过两个，那么就有解，否则无解。

然鹅赛时交上去 WA 了。我就想，可能有的情况是不符合的。因此我就随便找了一个点进行广搜，如果能搜到所有点那么就有解，否则无解。

然后赛后又被 hack 了，详见这篇帖子。

既然这样就找一条链呗，这其实等价于在图上找一条哈密尔顿路径。

采用状压 DP 实现的时间复杂度 O(n^22^n)，n\le 8 的情况下应该比全排列优那么一点吧。