HDU 2144 Evolution：DNA 相似度分組 (並查集 + 暴力 LCS)

問題描述

N 種生物 (N≤100)，每種有 DNA 字符串 (長≤100，字符集 {A,C,G,T})。若兩 DNA 存在公共子串，長度超過兩者長度的 P% (P<100)，則視為相似。相似具有傳遞性（A~B, B~C ⇒ A~C 同群）。求最終分群數。

解題策略

1. 並查集維護分群
2. 任意兩物種檢查是否相似：求最長公共子串 (LCS) 長度
3. 若 100*LCS/len1 > P 且 100*LCS/len2 > P → 合併群
4. 最終統計並查集根節點數

暴力 LCS 實現

長度 ≤100，O(L1×L2×min(L1,L2)) ≈ 10^6 操作/對，共 ≤4950 對，總計 ~5×10^9 可能超時。但實測常數極小且可提前剪枝（當前最大已超過閾值即停止），實際極快。

核心代碼

#include <cstdio>
#include <cstring>
using namespace std;

const int N = 105;
int fa[N], n;
char dna[N][N];
int len[N];

int find(int x) { return x==fa[x]?x:fa[x]=find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = find(y); }

int main() {
    double P; int cs = 0;
    while (scanf("%d%lf", &n, &P) == 2) {
        for (int i=0; i maxL) maxL = l;
                        if (100.0*maxL/len[i] > P && 100.0*maxL/len[j] > P) {
                            unite(i, j); goto NEXT_PAIR;
                        }
                    }
                NEXT_PAIR: ;
            }
        int groups = 0;
        for (int i=0; i

優化要點

goto 提前跳出雙重循環，一旦滿足條件即合併
外層循環條件 maxL < len-si 剪枝：剩餘長度已無法超過當前最大
雙精度比較避免整數除法截斷誤差


樣例
輸入:
3 10.0
AAA
AA
CCC
輸出:
Case 1: 2
// AAA 與 AA LCS=2, 200%/3>10 且 200%/2>10 → 同群
// CCC 無相似 → 獨立群