前言
看到这道题,如果范围稍小一点,可以尝试将两串构造出来,然后连在一起,运用后缀排序求出hei数组进行求解,但很可惜的是,l和r太大了。
思考
我们先手造一下串
1 a
2 aba
3 abacaba
4 abacabadabacaba
...
会发现中点左右的串是一样的,比如[1,7]=[9,15],[4,6]=[12,14] (下标从一开始),也就是说如果左区间大于了某一个k,我们完全可以将其平移到左区间。如果要求的区间的右端点没有大于某一个中点,直接搜下去就可以了。如果和中点有交叉的话,这个时候就要分左右搜索,取最大值代码
#include<iostream> #include<algorithm> #include<cstring> #include<string> #include<cstdio> using namespace std; const int N=1e4+10; inline int dfs(int la,int ra,int lb,int rb,int k) {//a区间左右端点,b区间左右端点,构造串的长度 if(k<0) return 0; if(la>ra||lb>rb) return 0; if(la>lb) swap(la,lb),swap(ra,rb); //不合法 if(ra>=rb) return rb-lb+1; //区间之间相互包含 if(la==lb) return ra-la+1; int len=1<<k; if(lb>len) return dfs(la,ra,lb-len,rb-len,k); //可以直接左移 if(ra<len&&rb<len) return dfs(la,ra,lb,rb,k-1); //不用改变,接着搜 int ans; ans=max(dfs(la,ra,lb,len-1,k),dfs(la,ra,1,rb-len,k)); //有交叉 return max(ans,ra-lb+1); //交叉部分,即有重叠的部分直接算出长度 } int main() { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); printf("%d\n",dfs(a,b,c,d,30)); return 0; }