题意

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

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

  分析

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

  代码

  #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;
  }