题意

给你一个字符串的生成方式,求问 的最长公共子序列。

  • 第一步时字符串仅包含单个字符
  • 在第 步中,我们将第 步中得到的字符串复制两次,并在这两个串中间插入字母表中的第 个字符。

    分析

    无论任何时候这个串都是一个回文串,且第 步时,回文中心是 。那么可以递归构造这两个字符串。那么讨论这个串左右端点和回文中心的位置关系递归下去。注意边界问题。时间复杂度为

    代码

    #include<bits/stdc++.h>
    using namespace std;
    int solve(int l1,int r1,int l2,int r2,int S){
      if(r1 - l1 < 0 || r2 - l2 < 0) return 0;
      int L = max(l2,l1),R = min(r1,r2);
      int res = (L <= R) ? R - L + 1 : 0;
      if((l1 <= l2 && r2 <= r1)||(l2 <= l1 && r1 <= r2)) return res;
      int mid = 1 << S;
      res = max(res,solve(min(l1,mid),min(r1,mid-1),min(l2,mid),min(r2,mid-1),S-1));
      res = max(res,solve(min(l1,mid),min(r1,mid-1),max(l2,mid+1)-mid,max(r2,mid)-mid,S-1));
      res = max(res,solve(max(l1,mid+1)-mid,max(r1,mid)-mid,min(l2,mid),min(r2,mid-1),S-1));
      res = max(res,solve(max(l1,mid+1)-mid,max(r1,mid)-mid,max(l2,mid+1)-mid,max(r2,mid)-mid,S-1));
      return res;
    }
    int main()
    {
      int l1,l2,r2,r1;
      cin >> l1 >> r1 >> l2 >> r2;
      int ans = solve(l1,r1,l2,r2,29);
      cout << ans << endl;
      return 0;
    }