CF161C Abracadabra

• 题意：大概是给你一个字符串，他是又以下规则生成的
  首先第一步，整个字符串为a，然后有36个字符从a到z到0到9
  第二步，首先在前一步得到的字符串后面加一个字符，第二步就+b
  然后把前一步得到的字符串再复制一遍添到b后面
  比如，第一步是a, 第二步就变成了aba，依此变下去
  然后经过30步，会得到一个很长的字符串
  问题给你la, ra, lb, rb要求在原串中从la到ra字符复制出来用字符串s1表示
  从原串中从lb到rb复制出来用字符串s2表示
  要求s1和s2的最长公共子串
• 思路:2^30内的字符中，2^29上的字符一定是唯一的
  如果最大相同子串包含这个字符，那么最大子串一定是重叠的部分，
  否则它把两个区间分别分成两部分，这两部分可以分别算出重复的最大子串
  然后找出最大值。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=510;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

int dfs(int l1,int r1,int l2,int r2,int k){
    if(l1>r1) return 0;
    if(l2>r2) return 0;
    if(l1>l2||l1==l2&&r1<r2) swap(l1,l2),swap(r1,r2);
    if(r1>=r2) return r2-l2+1;
    int len=1<<k;
    if(l2>len) return dfs(l1,r1,l2-len,r2-len,k);
    if(r1<len&&r2<len) return dfs(l1,r1,l2,r2,k-1);
    int ans=max(dfs(l1,r1,l2,len-1,k),dfs(l1,r1,1,r2-len,k));
    return max(ans,r1-l2+1);
}

void solve(){    
    int l1,r1,l2,r2;
    cin>>l1>>r1>>l2>>r2;
    cout<<dfs(l1,r1,l2,r2,30)<<"\n";
}


int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef DEBUG
    freopen("F:/laji/1.in", "r", stdin);
//    freopen("F:/laji/2.out", "w", stdout);
#endif
//     int t;cin>>t;while(t--)
    solve();
    return 0;
}