CF1789F题解

tangtianyao0123 · 2025-09-26 19:39:42 · 题解

一道人类智慧题

正文

考虑枚举 k，拼凑两个暴力：

1. 将 S 划分成 k 个部分，对于每个部分求 LCS，复杂度 O(C_n^k\times n^{k - 1})（O(n^{2k-1}) 是假的），能跑过 k \le 3。
2. 将 S 划分成长度为 \displaystyle \frac{n}{k} 的串，则 T' 一定是某个部分的子串。 :::info[证明] 考虑反证法。如果不是子序列，则说明跨度 > \displaystyle \frac{n}{k}。又因为有 k 段，所以跨度 > n，矛盾。 ::: 所以我们考虑求每个部分的子串，贪心匹配求答案即可。复杂度 O(nk2^{ \frac{n}{k}})，能跑过 k \ge 5，而在写代码中你只用考虑 k = 5 时（可以自己想想为什么）

那 k=4 时，怎么办呢？显然，答案字符串 T = T'+T'+T'+T'=(T'+T')+(T'+T')，在 k=2 时算过，所以不用管，然后就做完了。 :::success[code]

#include <bits/stdc++.h>

using namespace std;

string s;
int n, m, f[81][81], f2[81][81][81], ans;

int LSC1(string &s, string &t){//求两个字符串的LCS，传引用更快
  memset(f, 0, sizeof f);//清空
  int l1 = s.size(), l2 = t.size();
  s = ' ' + s, t = ' ' + t;//转移下标
  for(int i = 1; i <= l1; i++){
    for(int j = 1; j <= l2; j++){
      if(s[i] == t[j])
        f[i][j] = f[i - 1][j - 1] + 1;
      f[i][j] = max({f[i][j], f[i - 1][j], f[i][j - 1]});
    }
  }//普通的nm求解
  return f[l1][l2];
}

int LSC2(string &s, string &t, string &r){//求三个字符串的LCS，传引用更快
  memset(f2, 0, sizeof f2);//清空
  int l1 = s.size(), l2 = t.size(), l3 = r.size();
  s = ' ' + s, t = ' ' + t, r = ' ' + r;//转移下标
  for(int i = 1; i <= l1; i++){
    for(int j = 1; j <= l2; j++){
      for(int k = 1; k <= l3; k++){
        if(s[i] == t[j] && t[j] == r[k])
          f2[i][j][k] = f2[i - 1][j - 1][k - 1] + 1;
        f2[i][j][k] = max({f2[i][j][k], f2[i - 1][j][k], f2[i][j - 1][k], f2[i][j][k - 1]});
      }
    }
  }
  return f2[l1][l2][l3];
}

string t, s1;//枚举s1的子串t

void dfs(int x){
  if(x == s1.size()){
    int p = 0, sz = t.size(), cnt = 0;
    if(sz > 0){
      for(char c : s){
        if(c == t[p]){
          cnt += p == sz - 1;
          p = (p + 1) % sz;
        }
      }
    }//贪心匹配
    if(cnt < 2) cnt = 0;//必须至少出现两次
    ans = max(ans, sz * cnt);
    return ;
  }
  dfs(x + 1);
  t.push_back(s1[x]);
  dfs(x + 1);
  t.pop_back();
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> s;
  n = s.size();
  for(int i = 0; i < n; i++){
    string t1 = s.substr(0, i), t2 = s.substr(i);
    ans = max(ans, 2 * LSC1(t1, t2));
  }
  for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
      string t1 = s.substr(0, i), t2 = s.substr(i, j - i), t3 = s.substr(j);
      ans = max(ans, 3 * LSC2(t1, t2, t3));
    }
  }
  int m = (n + 4) / 5;//一定得向上取整，不然会WA最后一个点，有点玄学
  for(int i = 0; i < n; i += m){
    s1 = s.substr(i, m);
    dfs(0);
  }
  cout << ans;
  return 0;
}

:::