CF161C

C. Abracadabra

给定字符串a，进行以下操作：
将字符串的结尾插入b（操作次数对应的字符），以b为对称中心构造回文串，得到aba。
上述操作进行到第30次。
a为第一次操作。
b～z对应2～26，0～9对应27～36。
给定,求最长公共子串的长度。

Solution

首先这是一个回文串，且由于操作次数小于36，故对称中心唯一。
根据回文串的性质这个答案，可以分治递归将其向左对称缩小长度。
答案为缩小到有重叠部分时的。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 1e6 + 5;

int solve(int a,int b,int c,int d,int k){
    if(a>b || c>d) return 0;
    if(a>c || (a==c && b<d)) swap(a,c),swap(b,d);
    if(b>=d) return d-c+1;
    if(a==c) return b-a+1;
    int l=1<<k;
    if(c>l) return solve(a,b,c-l,d-l,k);
    if(b<l and d<l) return solve(a,b,c,d,k-1);
    return max({solve(a,b,c,l-1,k),solve(1,d-l,a,b,k),b-c+1});
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int a,b,c,d;
    cin>>a>>b>>c>>d;
    cout<<solve(a,b,c,d,30)<<'\n';
    return 0;
}