P14448 题解

· · 题解

题意

给出一个三色序列，可选择一个区间并任意重排其中的元素，要求最终序列相邻元素不同，求所选区间的最短长度。判断无解，构造方案。多组数据，\sum n\le 2\times 10^6。

题解

不难发现当且仅当最大出现次数 t 满足 2t-1\gt n 时无解，初始合法也容易判断，先判掉。之后对于原序列每对相邻相等元素 i,i+1，操作区间至少要覆盖两者之一。于是取这种元素的 \min(i)+1 作为 L，\max(i) 作为 R，则合法操作区间一定满足 l\le L,r\ge R。注意此处可能有 L=R+1，不过没有影响。

还需要具体判断区间是否合法。对于某种颜色 c，设 s_i 表示前缀 i 中 c 的出现次数，则对字符 c 来说区间 [l,r] 合法当且仅当 2(s_r-s_{l-1})-1\le {r-l+1-[a_{l-1}=c]-[a_{r+1}=c]}，实际意义与 2t-1\gt n 是类似的。移项并整理可得 (r-[a_{r+1}=c]-2s_r)+(2s_{l-1}-l-[a_{l-1}=c])\ge -2。设两括号内的式子分别为 g_r,f_l，合法条件即 g_r+f_l\ge -2，非常简洁啊！

之后对于最小操作区间 [L,R]，先用该方式判断三种颜色是否合法，可以发现非法颜色最多只会有一种。对该颜色尝试将区间向两边扩展，讨论一下可以发现此时 f,g 分别单调，双指针即可求出最短的操作区间。至于构造方案，每次填当前剩余次数最大的颜色即可，有多种时优先选 a_{r+1} 就好了，复杂度 \mathcal O(n)。

代码

#include<iostream>
using namespace std;
const int N=2e6+10;
int n,L,R,a[N],b[N][3],c[N],f[N],g[N];
string s; char ch[3]={'C','W','P'};
void print(int l,int r)
{
    for(int i=1;i<l;i++) cout<<s[i];
    int t[3],last=a[l-1];
    for(int j=0;j<3;j++) t[j]=b[r][j]-b[l-1][j];
    for(int i=l;i<=r;i++)
    {
        int mx=-1,c=-1;
        for(int j=0;j<3;j++) if(last!=j&&(t[j]>mx||(t[j]==mx&&a[r+1]==j))) mx=t[j],c=j;
        cout<<ch[c],t[c]--,last=c;
    }
    for(int i=r+1;i<=n;i++) cout<<s[i];
    cout<<'\n';
}
void sol()
{
    cin>>n>>s,s=" "+s,L=R=0,a[0]=a[n+1]=-1;
    for(int i=1;i<=n;i++) a[i]=(s[i]=='C'?0:(s[i]=='W'?1:2));
    for(int i=1;i<n;i++) if(a[i]==a[i+1]) R=i;
    for(int i=n;i>1;i--) if(a[i]==a[i-1]) L=i;
    if(!R) {cout<<"Beautiful\n"; return;}
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<3;j++) b[i][j]=b[i-1][j];
        b[i][a[i]]++;
    }
    if(max(b[n][0],max(b[n][1],b[n][2]))>(n+1)/2) {cout<<"Impossible\n"; return;}
    cout<<"Possible\n";
    for(int j=0;j<3;j++)
    {
        int ts=R-L-(a[L-1]==j)-(a[R+1]==j)-(b[R][j]-b[L-1][j])*2;
        if(ts<-2)
        {
            ts=-ts,g[R-1]=-N*3;
            for(int i=L;i;i--) f[i]=2*b[i-1][j]-i-(a[i-1]==j);
            for(int i=R;i<=n;i++) g[i]=i-(a[i+1]==j)-2*b[i][j];
            int tp=n+1,mx=-N,rl=-N,rr=N; 
            for(int i=L;i;i--) if(f[i]>mx)
            {
                mx=f[i];
                while(g[tp-1]+f[i]>=-2) tp--;
                if(tp<=n&&tp-i<rr-rl) rr=tp,rl=i;
            }
            cout<<rl<<' '<<rr<<'\n',print(rl,rr); return;
        }
    }
    cout<<L<<' '<<R<<'\n',print(L,R);
}
signed main()
{
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int TT; cin>>TT;
    while(TT--) sol(); 
    return 0;
}