题解：CF178F1 Representative Sampling

lgx57 · 2025-02-19 18:35:26 · 题解

为什么题解区全部都是可以过 F2，F3 的做法啊？这里来一个只能过 F1 的做法。

我们提前把字符串两两之间的 \operatorname{lcp} 求出来，然后直接暴力枚举子集。注意枚举时如果不是 k 元子集直接跳过。

时间复杂度：O(C_{n}^k k^2)。可以通过本题。

void sol(){
    int n,k;
    cin>>n>>k;
    for (int i=1;i<=n;i++) cin>>s[i];
    for (int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            if (i==j) continue;
            if (i>j){
                a[i][j]=a[j][i];
                continue;
            }
            int now=0;
            while (s[i][now]==s[j][now]&&now<min(sz(s[i]),sz(s[j]))) now++;
            a[i][j]=now;//lcp
        }
    }
    int ans=0;
    for (int i=0;i<(1<<n);i++){
        if (__builtin_popcount(i)!=k) continue;
        vector<int> v;
        for (int j=0;j<n;j++){
            if ((i>>j)&1) v.pb(j+1);
        }
        int sum=0;
        for (int j=0;j<k-1;j++){
            for (int l=j+1;l<k;l++){
                sum+=a[v[j]][v[l]];
            }
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
}