CF161C Abracadabra

分治

很恶心的那种

观察到我们每一层都是一个回文串而且回文中心很显然,又因为每次变小一半,所以可以考虑分治

我们首先把两个区间分成四类情况

都在左/右边区间

解决方法直接递归即可

分在左右两侧

解决方法把一个按照回文串的性质对称到另一侧即可

两个都过了中间

解决方法把能匹配的位置匹配掉,然后挂到两个串的左右,表示前继匹配长度

一个过了中间

解决方法把小的翻到大的一侧,因为你会发现匹配长度一定不会

于是你qaq因为显然不能很简单的写出来了

我们考虑把其中本质相同的合并一下

跨过中间的可以合并成一种情况!

变成左边和左边的匹配,右边和右边的匹配,那么其实只是用mid去截一半

写的时候你会发现这个东西可以用四个minmax之类的式子省去分类讨论

code:


#include<bits/stdc++.h>
using namespace std;

int l1, l2, r2, r1, ans;
inline void solve(int L, int R, int l1, int r1, int l2, int r2, int Lh1, int Rh1, int Lh2, int Rh2) {
	if(R < L) {
		ans = max(ans, Lh1);
		ans = max(ans, Rh1);
		ans = max(ans, Lh2);
		ans = max(ans, Rh1);
		return ;
	}
	int mid = (L + R) >> 1;
	// printf("%d %d %d %d %d %d %d %d %d %d %d \n", L, mid, R, l1, r1, l2, r2, Lh1, Rh1, Lh2, Rh2);

	if(r1 < mid && r2 < mid)solve(L, mid - 1, l1, r1, l2, r2, Lh1, Rh1, Lh2, Rh2);
	if(l1 > mid && l2 > mid)solve(L, mid - 1, 2 * mid - r1, 2 * mid - l1, 2 * mid - r2, 2 * mid - l2, Rh1, Lh1, Rh2, Lh2); //第一类,均两侧
	if(l1 > mid && r2 < mid)solve(L, mid - 1, 2 * mid - r1, 2 * mid - l1, l2, r2, Rh1, Lh1, Lh2, Rh2);
	if(l2 > mid && r1 < mid)solve(L, mid - 1, l1, r1, 2 * mid - r2, 2 * mid - l2, Lh1, Rh1, Rh2, Lh2); //第二类,对折齐
	//l1小,l2大
	if(l1 <= mid && r1 >= mid) {
		if(l2 <= mid && r2 >= mid) {//第三类,均居中
			int tmpl = max(l1, l2);
			int tmpr = min(r1, r2);
			if(tmpl == l1)Lh1 += tmpr - tmpl + 1;
			else Lh2 += tmpr - tmpl + 1;
			if(tmpr == r1)Rh1 += tmpr - tmpl + 1;
			else Rh2 += tmpr - tmpl + 1;
			if((tmpl == l1 && tmpr == r1) || (tmpl == l2 && tmpr == r2)) {
				ans = max(ans, Lh1);
				ans = max(ans, Rh1);
				return ;
			}
			// printf("qwq?l1?%d r1?%d l2?%d r2?%d %d %d %d %d %d %d\n", l1, tmpl - 1, 2 * mid - r2, 2 * mid - (tmpr + 1), tmpl, tmpr, Lh1, Rh1, Lh2, Rh2);
			// assert(0);
			solve(L, mid - 1, l1, tmpl - 1, 2 * mid - r2, 2 * mid - (tmpr + 1), Lh1, Rh1, Rh2, Lh2);
		} else {
			if(r2 <= mid) {
				//第四类,小入大
				if(l1 == r1 && l1 == mid) {
					ans = max(ans, Lh1);
					ans = max(ans, Rh1);
					return;
				}
				// printf("qWq?l1?%d r1?%d l2?%d r2?%d %d %d %d %d\n", 2 * mid - r1, 2 * mid - (mid + 1), l2, r2, Lh1, Rh1, Lh2, Rh2);
				if(r1 - mid + 1 > mid - l1 + 1)solve(L, mid - 1, 2 * mid - r1, 2 * mid - (mid + 1), l2, r2, Rh1, Lh1, Lh2, Rh2);
				else solve(L, mid - 1, l1, mid - 1, l2, r2, Lh1, Rh1, Lh2, Rh2);
			} else {
				if(l1 == r1 && l1 == mid) {
					ans = max(ans, Lh1);
					ans = max(ans, Rh1);
					return;
				}
				// printf("Qwq?l1?%d r1?%d l2?%d r2?%d %d %d %d %d\n", 2 * mid - r1, 2 * mid - (mid + 1), 2 * mid - r2, 2 * mid - l2, Lh1, Rh1, Lh2, Rh2);
				if(r1 - mid + 1 > mid - l1 + 1)solve(L, mid - 1, 2 * mid - r1, 2 * mid - (mid + 1), 2 * mid - r2, 2 * mid - l2, Rh1, Lh1, Rh2, Lh2);
				else solve(L, mid - 1, l1, mid - 1, 2 * mid - r2, 2 * mid - l2, Lh1, Rh1, Rh2, Lh2);
			}
		}
	} else if(l2 <= mid && r2 >= mid) {//也是第四类
		if(r1 <= mid) {
			if(l2 == r2 && l2 == mid) {
				ans = max(ans, Lh1);
				ans = max(ans, Rh1);
				return ;
			}
			// printf("qAq?l1?%d r1?%d l2?%d r2?%d %d %d %d %d\n", l1, r1, 2 * mid - r2, 2 * mid - (mid + 1), Lh1, Rh1, Lh2, Rh2);
			if(r2 - mid + 1 > mid - l2 + 1)solve(L, mid - 1, l1, r1, 2 * mid - r2, 2 * mid - (mid + 1), Lh1, Rh1, Rh2, Lh2);
			else solve(L, mid - 1, l1, r1, l2, mid - 1, Lh1, Rh1, Lh2, Rh2);
		} else {
			if(l2 == r2 && l2 == mid) {
				ans = max(ans, Lh1);
				ans = max(ans, Rh1);
				return ;
			}
			// printf("Qaq?l1?%d r1?%d l2?%d r2?%d %d %d %d %d\n", 2 * mid - r1, 2 * mid - l1, 2 * mid - r2, 2 * mid - (mid + 1), Lh1, Rh1, Lh2, Rh2);
			if(r2 - mid + 1 > mid - l2 + 1)solve(L, mid - 1, 2 * mid - r1, 2 * mid - l1, 2 * mid - r2, 2 * mid - (mid + 1), Rh1, Lh1, Rh2, Lh2);
			else solve(L, mid - 1, 2 * mid - r1, 2 * mid - l1, l2, mid - 1, Rh1, Lh1, Lh2, Rh2);
		}
	}
}

inline int solve2(int k, int l1, int r1, int l2, int r2) {
	printf("%d %d %d %d\n", l1, r1, l2, r2);
	if(r1 - l1 < 0 || r2 - l2 < 0)return 0;
	int L = max(l1, l2);
	int 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 << k);
	res = max(res, solve2(k - 1, min(l1, mid), min(r1, mid - 1), min(l2, mid), min(r2, mid - 1)));
	res = max(res, solve2(k - 1, min(l1, mid), min(r1, mid - 1), max(l2, mid + 1) - mid, max(r2, mid) - mid));
	res = max(res, solve2(k - 1, max(l1, mid + 1) - mid, max(r1, mid) - mid, min(l2, mid), min(r2, mid - 1)));
	res = max(res, solve2(k - 1, max(l1, mid + 1) - mid, max(r1, mid) - mid, max(l2, mid + 1) - mid, max(r2, mid) - mid));
	return res;
}

int main() {
	scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
	//第几层,左边区间,右边区间
	printf("%d\n", solve2(29, l1, r1, l2, r2));
	return 0;
}

夏晓光(loveJY)的博客

CF1227G Not Same