CF161C Abracadabra 分治

Abracadabra 分治"/>

CF161C Abracadabra 分治

链接
题意
给定一个字符串的构造方式：首先只有一个字符串 a ，然后赋值这个字符串串联在后面，并在中间插入一个下一个字符。
a
aba
abacaba
abacabcdabacaba
…
总共26个小写英文加上10个数字，规定数字比字母大，即0=‘z’+1，1=‘z’+2 …
给定l1 , r1 , l2 , r2 两个该字符串的子串，求最长公共子串长度。（1 ≤ li ≤ ri ≤ 1e9）
题解
首先很容易发现，原字符串是回文串，且长度为2 ^ k - 1，k为字符个数，中间的字符唯一。根据中间的字符进行求解，原问题是在长度为2 ^ k - 1的字符串中找l1,r1,l2,r2的最长公共子串长度，假如这两个字符串有重叠且重叠部分没有那个中间字符，那么答案就是min(r1,r2) - max(l1,l2) ， 如果有，那就要分类讨论，将串1和串2从中间字符分别分成两部分，2*2枚举情况，并用子问题求解即可，在求解过程中，如果串1包含串2或者串2包含串1，那么直接输出被包含串的长度。
代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 7;
typedef long long ll;
int solve(int l1, int r1, int l2, int r2, int k) {if(r1 < l1 || r2 < l2) return 0;if(k < 0) return 0;int ans = min(r1, r2) - max(l1, l2) + 1;if(l1 <= l2 && r1 >= r2) return ans = r2 - l2 + 1;if(l2 <= l1 && r2 >= r1) return ans = r1 - l1 + 1;int mid = (1<<k);if(l1 > mid) l1 -= mid, r1 -= mid;//将两个子串都移到特殊子符左边，因为原串的特殊性，不影响答案，方便求解。if(l2 > mid) l2 -= mid, r2 -= mid;ans = max(ans, solve(l1, min(r1, mid - 1), l2, min(r2, mid - 1), k - 1));if(r2 > mid) ans = max(ans, solve(l1, min(r1, mid - 1), 1, r2 - mid, k - 1));if(r1 > mid) {ans = max(ans, solve(1, r1 - mid, l2, min(r2, mid - 1), k - 1));if(r2 > mid) ans = max(ans, solve(1, r1 - mid, 1, r2 - mid, k - 1));}return ans;
}
int main() {int l1, l2, r1, r2;scanf("%d%d%d%d", &l1, &r1, &l2, &r2);printf("%d\n", solve(l1, r1, l2, r2, 30));
}