题意
给你一个字符串的生成方式,求问 和 的最长公共子序列。
- 第一步时字符串仅包含单个字符
- 在第 步中,我们将第 步中得到的字符串复制两次,并在这两个串中间插入字母表中的第 个字符。
分析
无论任何时候这个串都是一个回文串,且第 步时,回文中心是 。那么可以递归构造这两个字符串。那么讨论这个串左右端点和回文中心的位置关系递归下去。注意边界问题。时间复杂度为 。代码
#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; }