题解：P12571 [UOI 2023] An Array of Characters and Almost Palindromes【交互库尚未配置】

· · 题解

本题的提交窗口。

最近总是败给这种一个小观察的题。= =

能够重排成回文串，意味着至多一个字符出现了奇数次。我们只需要保留下一个最长的区间使得至多一个字符出现了奇数次。

判掉区间本身就不行，考虑到 Subtask 9 的提示性，我们发现如果没有任何一个字符出现奇数次，删去首尾中的一个就能规约到有一个字符出现了奇数次。

于是考虑有一个字符出现了奇数次怎么做。

有结论：一定删除这个字符偶数次再删恰好一个别的字符。

我们当然也可以删除这个字符奇数次，再删两种别的字符。但这显然是不优的：我要么不必删这个字符奇数次，要么不必多删一种别的字符。

于是只需考虑最少要删这个字符多少次可以删到别的字符。把两头拿出来讨论一下就好了。

int n;
char s[N];
int q;
int nxt[N][26],pre[N][26];
int solve(int l,int r,int c){
    int nl=nxt[l][c];
    int nr=pre[r][c];
    if(r-nr<l+nl) return 0;
    else{
        int ans=0;
        if(!(nl&1)) ans=max(ans,r-l+1-nl-1);
        else if(nr) ans=max(ans,r-l+1-nl-2);
        if(!(nr&1)) ans=max(ans,r-l+1-nr-1);
        else if(nl) ans=max(ans,r-l+1-nr-2);
        return ans;
    }
}
int xr[N];
#define pc __builtin_popcount
int main(){
#ifdef Shun
    freopen(".in","r",stdin);
    freopen(".out","w",stdout);
#endif
    ios::sync_with_stdio(false);    
    cin>>n;
    fr1(i,1,n) cin>>s[i];
    fr1(i,1,n){
        pre[i][s[i]-'a']=pre[i-1][s[i]-'a']+1;
    }
    fr2(i,n,1){
        nxt[i][s[i]-'a']=nxt[i+1][s[i]-'a']+1;
    }
    fr1(i,1,n) xr[i]=xr[i-1]^(1<<s[i]-'a');
    cin>>q;
    while(q--){
        int l,r;
        cin>>l>>r;
        if(pc(xr[r]^xr[l-1])>=2) cout<<r-l+1<<endl;
        else if(pc(xr[r]^xr[l-1])==1) cout<<solve(l,r,__lg(xr[r]^xr[l-1]))<<endl;
        else{
            cout<<max(solve(l+1,r,__lg(xr[r]^xr[l])),solve(l,r-1,__lg(xr[r-1]^xr[l-1])))<<endl;
        }
    }
    ET;
}
//ALL FOR Zhang Junhao.