题解：B4392 [常州市赛 2025] 压缩

提供一种简单的方法。

思路

我们定义一个答案字符数组

a

，用

k

表示其当前的长度。我们遍历原字符串，设当前遍历到第

i

位，如果

s_i

与

a_k

不相同且

s_i

不是通配符，那么令

a_{k+1}=s_i

。

因为答案的长度最多为

3

，所以如果

k

达到了

4

，就说明一定可以消除，比如 1010 或 0101。那么我们可以直接让

k=2

，即保留前两位。同理，如果此时

k=3

且当前遍历的

s_i

为通配符，如 101#，此时的情况相当于

k=4

，我们同样令

k=2

即可。

遍历完后我们需要再特判一下，如果

s_0

为通配符且

k=3

，如 #101，这种情况同样相当于

k=4

，只是我们保留后两位即可。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
int k;
string s;
char a[5];
int main(){
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(a[k]!=s[i]&&s[i]!='#'){
			a[++k]=s[i];
			if(k==4||(k==3&&s[i]=='#')){
				k=2;
			}
		}
	}
	if(s[0]=='#'&&k==3){
		for(int i=2;i<=3;i++){
			cout<<a[i];
		}
		return 0;
	}
	for(int i=1;i<=k;i++){
		cout<<a[i];
	}
}

题解：B4392 [常州市赛 2025] 压缩

文章操作

思路

代码

相关推荐

评论

题解：B4392 [常州市赛 2025] 压缩