题解 | #不是烤串故事#

这有 2200？？？

注意到操作是平凡的，我们直接维护整个串的翻转，那么操作就可以简单表示，又因为 lcp 是具有单调性的，考虑二分。于是对于每个 ，我们可以二分 lcp 的值，然后对于每个二分出来的值，假设当前在处理 的答案，二分的答案是 ，如果 ，说明这一段全都是需要翻转的，直接处理。如果 ，说明有一段要翻转有一段不翻，我们分开处理即可。

要做到 判断答案合法性，显然考虑哈希，于是我们使用二分+哈希就做完了，思路可以说非常简单，所涉及到的思想和算法也都比较简单，感觉完全没有 2200。代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll mod=998244353;
const ll B=1331;
ll n,h1[1000005],h2[1000005],h3[1000005],pw[1000005],ans,id;string a,b,s;
ll get1(ll l,ll r){
    return (h1[r]-h1[l-1]*pw[r-l+1]%mod+mod)%mod;
}
ll get2(ll l,ll r){
    return (h2[r]-h2[l-1]*pw[r-l+1]%mod+mod)%mod;
}
ll get3(ll l,ll r){
    return (h3[r]-h3[l-1]*pw[r-l+1]%mod+mod)%mod;
}
bool ck(ll x,ll y){
    if(x<=y){
        return (get2(n-y+1,n-y+x)==get3(1,x));
    }else{
        return (get2(n-y+1,n)==get3(1,y)&&get1(y+1,x)==get3(y+1,x));
    }
}
ll bs(ll x){
    ll l=0,r=n,res=0;
    while(l<=r){
        ll md=(l+r)>>1;
        if(ck(md,x)){
            l=md+1,res=md;
        }else{
            r=md-1;
        }
    }
    return res;
}
void solve(){
    cin>>n>>a>>s,b=a,a=" "+a,reverse(b.begin(),b.end()),b=" "+b,s=" "+s;
    h1[0]=h2[0]=h3[0]=1,ans=0,id=1;
    for(ll i=1;i<=n;i++) h1[i]=(h1[i-1]*B%mod+a[i])%mod;
    for(ll i=1;i<=n;i++) h2[i]=(h2[i-1]*B%mod+b[i])%mod;
    for(ll i=1;i<=n;i++) h3[i]=(h3[i-1]*B%mod+s[i])%mod;
    for(ll i=1;i<=n;i++){
        ll rt=bs(i);
        if(rt>ans) ans=rt,id=i;
    }
    cout<<ans<<" "<<id<<endl;
}
int main(){
    ll T;cin>>T;
    pw[0]=1;for(ll i=1;i<=1000000;i++) pw[i]=pw[i-1]*B%mod;
    while(T--) solve();
}