P14448

DDF_ · 2025-11-17 15:06:25 · 题解

Update：对语言进行了润色，增加了自己忘写了的情况。

题面

有一串长度为 n 的颜色序列 s，选一段最短区间，对其重排，使得整个序列没有相邻颜色相同的情况，求出这个区间并给出重排后的序列。

特判原序列就满足条件和无解。

题解

原序列就满足条件：枚举一遍序列，判断题目中的条件。

无解：注意到一个颜色如果很多的话就没办法重排使得其满足条件了，所以去考虑颜色数量的上限。手玩一下就是类似 \texttt{CWCPCWC} \cdots 中间隔一个同色的情况，此刻就有颜色就达到了上限。由此可得，颜色数量上限就是 \lceil \frac{n}{2} \rceil，超过这个上限就无解。

想一下怎么求最短序列，发现重排后能不能满足题目条件和序列长度中存在单调性，直接开始二分。

对于一个序列长度 x，枚举左端点 l，判断这一段 [l,l+x-1] 重排后能不能满足题目条件。

为了使后面的语言更易懂，令左端点为 l，右端点为 r=l+x-1。

首先是这一段区间需要满足重排后有解，即区间内不能有颜色超过上限。而且区间内的相邻同色个数一定要与整个序列的相邻同色个数相同（要把整个序列的同色对都拆开，注意 s_{l-1}=s_{l}、s_{r+1}=s_{r} 的情况也要算在内）。

其次，若有一个颜色达到颜色数量上限，进行分类讨论。

1. 若 x 奇，那么这个区间重排后，s_{l} 和 s_{r} 都是达到颜色数量上限的颜色，如果 s_{l-1} 和 s_{r+1} 中存在一个和这个颜色相同就无解。
2. 若 x 偶，那么这个区间重排后，s_{l} 和 s_{r} 至少有一个是达到颜色数量上限的颜色，如果 s_{l-1} 和 s_{r+1} 都与这个颜色相同就无解（注意此情况中，可能有 2 个颜色同时达到颜色数量上限）。

最后，若不存在颜色达到颜色数量上限，则不管 s_{l} 和 s_{r} 放什么颜色，都会满足去除左右端点的子区间 [l+1,r-1] 也有解。因为 s_{l} 和 s_{r} 可以放任意颜色，所以可以完全规避与 s_{l-1} 和 s_{r+1} 相同的情况，那么这样就是有解的。

::::warning[对于最后一种情况的证明]{open} 首先，[l,r] 没满足有颜色达到颜色数量上限就可以接着往端点随便放颜色（注意不要与 s_{l-1} 和 s_{r+1} 相同），然后令区间转变为 [l+1,r-1]，继续考虑内部子区间的情况。

一直往端点放颜色，到最后肯定会出现有颜色达到颜色数量上限的情况。由于之前在 [l,r] 往端点放颜色前没达到颜色数量上限，则往端点放颜色后 x\leftarrow x-2，对应的 \lceil\frac{x}{2}\rceil \leftarrow \lceil\frac{x}{2}\rceil-1，然而被放在端点的两个颜色数量各 -1，那么这两个颜色绝对不会到内部子区间的数量上限。所以区间变为 [l+1,r-1] 时仍旧有解。

考试的时候猜出来就行了。 ::::

构造就按照上述推导的过程，先往端点颜色直到有颜色达颜色数量上限，达到颜色数量上限后就按照间隔一个放顶到上限的颜色即可。

然后会发现这样构造终于把代码堆成了依托。所以我请出了贪心构造大法。

直接贪，放剩余颜色最多的，如果没法放最多的，优先放右端点后一个的（避免最后撞到），如果右端点后一个已经放完了或与剩余颜色最多的相同，再随便找一个往里面塞。

此题结。

代码

代码奇丑无比，加点注释希望能看懂。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+5;
const char ntl[4]={0,'C','P','W'}; // 数字转字母
unordered_map<char,int> ltn; //字母转数字
int _;
int n;
int ss[N]; //字母转数字后的序列
char s[N];
int cnt[N][6]; //0：前缀不相等数量，1/2/3分别为前缀 C P W 的数量
int q(int l,int r,int k) {
    r=min(r,n),l=max(1,l);
    if(k==-1) return 0;
    return cnt[r][k]-cnt[l-1][k];
} //通过前缀和算区间内的数量
int check(int x) {
    for(int l=1;l<=n-x+1;l++) {
        int r=l+x-1,mx=max(q(l,r,1),max(q(l,r,2),q(l,r,3)));
        if(q(l,r+1,0)==cnt[n][0]&&mx<=(r-l+2)/2) {
            int a=ss[r+1],b=ss[l-1];
            if(r+1>n) a=-1;
            if(l-1<1) b=-1;
            if(x&1) {
                if(mx<(r-l+2)/2) return l;
                if(q(l,r,a)!=mx&&q(l,r,b)!=mx) return l;
            }
            else {
                if(a!=b||mx<(r-l+2)/2) return l;
                if(q(l,r,a)!=mx) return l;
            }
        }
    }
    //return l 是要把左端点返回（不然怎么构造）
    return 0;
}
void solve() {
    cin>>n>>(s+1);
    for(int i=1;i<=n;i++) {
        cnt[i][1]=cnt[i-1][1],cnt[i][2]=cnt[i-1][2],cnt[i][3]=cnt[i-1][3],cnt[i][0]=cnt[i-1][0];
        ss[i]=ltn[s[i]],cnt[i][ltn[s[i]]]++;
        if(s[i]==s[i-1]) cnt[i][0]++;
    }
    if(max(cnt[n][1],max(cnt[n][2],cnt[n][3]))>(n+1)/2) {cout<<"Impossible"<<endl;return;}
    if(cnt[n][0]==0) {cout<<"Beautiful"<<endl;return;}
    cout<<"Possible"<<endl;
    int l=1,r=n;
    while(l<r) {
        int mid=(l+r)/2;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    int st=check(l),ed=st+l-1;
    cout<<st<<" "<<ed<<endl;
    int cns[4]={0,q(st,ed,1),q(st,ed,2),q(st,ed,3)},mx=max(cns[1],max(cns[2],cns[3])); //cns 是这段区间内剩余的可放置 C P W 个数。
    int xx=st,yy=ed;
    while(mx<(yy-xx+2)/2) {
        for(int i=1;i<=3;i++) if(cns[i]&&i!=ss[xx-1]) {ss[xx]=i,s[xx]=ntl[i],cns[i]--;break;}
        for(int i=1;i<=3;i++) if(cns[i]&&i!=ss[yy+1]) {ss[yy]=i,s[yy]=ntl[i],cns[i]--;break;}
        xx++,yy--;
        mx=max(cns[1],max(cns[2],cns[3]));
    } //左右端点放置，枚举放 C/P/W
    int x,y=ss[yy+1];
    if(yy==n) y=0;
    for(int i=1;i<=3;i++) if(cns[i]==mx) x=i;
    if(cns[x]==cns[y]) x=y; //偶数会有 2 个顶上限，如果一个是右端点后面那一个，先放右端点后面那一个的 
    for(int i=xx;i<=yy;i++) {
        if(ss[i-1]!=x) ss[i]=x,s[i]=ntl[x],cns[x]--;
        else {
            if(cns[y]&&y!=x) ss[i]=y,s[i]=ntl[y],cns[y]--; //优先处理右端点后面那一个，避免长度偶数时最后会与右端点撞 
            else for(int j=1;j<=3;j++) if(cns[j]&&j!=x&&j!=y) {ss[i]=j,s[i]=ntl[j],cns[j]--;break;}
        }
    }
    cout<<(s+1)<<endl;
    return;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    ltn['C']=1,ltn['P']=2,ltn['W']=3;
    cin>>_;
    while(_--) solve();
    return 0;
}

贪心构造法代码：

    for(int i=1;i<st;i++) cout<<s[i];
    int cns[4]={0,q(st,ed,1),q(st,ed,2),q(st,ed,3)};
    int y=ss[ed+1],lst=ss[st-1],x=0;
    if(ed==n) y=0;
    if(st==1) lst=0;
    for(int i=st;i<=ed;i++) {
        for(int j=1;j<=3;j++) if(cns[j]>cns[x]) x=j;
        if(cns[x]==cns[y]) x=y;
        if(lst!=x) cout<<ntl[x],cns[x]--,lst=x;
        else {
            if(cns[y]&&x!=y) cout<<ntl[y],cns[y]--,lst=y;
            else for(int j=1;j<=3;j++) if(x!=j&&y!=j&&cns[j]) {cout<<ntl[j],cns[j]--,lst=j;break;}
        }
    }
    for(int i=ed+1;i<=n;i++) cout<<s[i];
    cout<<endl;
    return;

（用这个替换掉 cout<<st<<" "<<ed<<endl; 后面的代码即可）