专栏文章

P14448

DDDF_
P14448题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min6cksd
此快照首次捕获于
2025/12/01 21:17
3 个月前
此快照最后确认于
2025/12/01 21:17
3 个月前
查看原文
Update：对语言进行了润色，增加了自己忘写了的情况。

题面

有一串长度为 nn 的颜色序列 ss，选一段最短区间，对其重排，使得整个序列没有相邻颜色相同的情况，求出这个区间并给出重排后的序列。
特判原序列就满足条件和无解。

题解

原序列就满足条件：枚举一遍序列，判断题目中的条件。
无解：注意到一个颜色如果很多的话就没办法重排使得其满足条件了，所以去考虑颜色数量的上限。手玩一下就是类似 CWCPCWC⋯\texttt{CWCPCWC} \cdots 中间隔一个同色的情况，此刻就有颜色就达到了上限。由此可得，颜色数量上限就是 ⌈n2⌉\lceil \frac{n}{2} \rceil，超过这个上限就无解。
想一下怎么求最短序列，发现重排后能不能满足题目条件和序列长度中存在单调性，直接开始二分。
对于一个序列长度 xx，枚举左端点 ll，判断这一段 [l,l+x−1][l,l+x-1] 重排后能不能满足题目条件。
为了使后面的语言更易懂，令左端点为 ll，右端点为 r=l+x−1r=l+x-1。
首先是这一段区间需要满足重排后有解，即区间内不能有颜色超过上限。而且区间内的相邻同色个数一定要与整个序列的相邻同色个数相同（要把整个序列的同色对都拆开，注意 sl−1=sls_{l-1}=s_{l}、sr+1=srs_{r+1}=s_{r} 的情况也要算在内）。
其次，若有一个颜色达到颜色数量上限，进行分类讨论。
  1. 若 xx 奇，那么这个区间重排后，sls_{l} 和 srs_{r} 都是达到颜色数量上限的颜色，如果 sl−1s_{l-1} 和 sr+1s_{r+1} 中存在一个和这个颜色相同就无解。
  2. 若 xx 偶，那么这个区间重排后，sls_{l} 和 srs_{r} 至少有一个是达到颜色数量上限的颜色，如果 sl−1s_{l-1} 和 sr+1s_{r+1} 都与这个颜色相同就无解（注意此情况中，可能有 22 个颜色同时达到颜色数量上限）。
最后，若不存在颜色达到颜色数量上限，则不管 sls_{l} 和 srs_{r} 放什么颜色，都会满足去除左右端点的子区间 [l+1,r−1][l+1,r-1] 也有解。因为 sls_{l} 和 srs_{r} 可以放任意颜色，所以可以完全规避与 sl−1s_{l-1} 和 sr+1s_{r+1} 相同的情况，那么这样就是有解的。
对于最后一种情况的证明
首先，[l,r][l,r] 没满足有颜色达到颜色数量上限就可以接着往端点随便放颜色（注意不要与 sl−1s_{l-1} 和 sr+1s_{r+1} 相同），然后令区间转变为 [l+1,r−1][l+1,r-1]，继续考虑内部子区间的情况。
一直往端点放颜色，到最后肯定会出现有颜色达到颜色数量上限的情况。由于之前在 [l,r][l,r] 往端点放颜色前没达到颜色数量上限，则往端点放颜色后 x←x−2x\leftarrow x-2，对应的 ⌈x2⌉←⌈x2⌉−1\lceil\frac{x}{2}\rceil \leftarrow \lceil\frac{x}{2}\rceil-1，然而被放在端点的两个颜色数量各 −1-1，那么这两个颜色绝对不会到内部子区间的数量上限。所以区间变为 [l+1,r−1][l+1,r-1] 时仍旧有解。
考试的时候猜出来就行了。
构造就按照上述推导的过程，先往端点颜色直到有颜色达颜色数量上限，达到颜色数量上限后就按照间隔一个放顶到上限的颜色即可。
然后会发现这样构造终于把代码堆成了依托。所以我请出了贪心构造大法。
直接贪，放剩余颜色最多的，如果没法放最多的，优先放右端点后一个的（避免最后撞到），如果右端点后一个已经放完了或与剩余颜色最多的相同，再随便找一个往里面塞。
此题结。

代码

代码奇丑无比，加点注释希望能看懂。
CPP
#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;
}
贪心构造法代码：
CPP
	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; 后面的代码即可）

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...