题解：AT_abc237_h [ABC237Ex] Hakata

沉石鱼惊旋 · 2025-12-05 15:58:27 · 题解

一个经典结论，本质不同的回文子串只有 \mathcal O(n) 个。

因此，可以暴力取出这些回文子串。如果存在子串关系，则连边。

显然图构成了一张 DAG。我们想要知道的就是 DAG 上的最长反链长度。

根据 Dilworth 定理，可以转化成 DAG 上最小链覆盖。

而最小链覆盖又可以转化为，对图拆点拆成二分图，原图连边 u\to v 则二分图连边 in_u\to out_v，最小链覆盖即为点数减去二分图的最大匹配。

这个很好理解，每一个匹配相当于原图两个点绑一起了，少一个点。最后绑不动了，绑的一连串就是一条路径。

因此建出二分图后求最大匹配即可。

复杂度 \mathcal O(n^3)。

有一说一，瓶颈在建图上，应该是可以拿字符串算法优化的。

另外如果使用匈牙利算法，存在一种很好写的不用拆点的做法。参见 https://atcoder.jp/contests/abc237/submissions/71443780。其实本质就是存边是 in\to out，然后存的 \mathrm{match} 是 \mathrm{match}_{out}=in 的关系。