“蔚来杯“2022牛客暑期多校训练营（加赛） G题: Good red-string

G题: Good red-string

原题链接:https://ac.nowcoder.com/acm/contest/38727/G

题目大意

定义由若干不相交的"red"序列构成的字符串为好red字符串。
例如redred是好red字符串，redrde不是好red字符串。

给定由’r’,‘e’,‘d’,'?‘构成的字符串，求能否将’?‘任意替换为’r’,‘e’,‘d’，使得字符串为好red字符串。

题解

设 $cn{t}_x$ 表示 $x$ 的数量。
考虑一个简化版的问题:括号序列匹配。
一个括号序列需要满足的条件是:

1. 对于任何前缀， $cn{t}_{(}\ge cn{t}_{)}$ 。
2. 对于整个字符串， $cn{t}_{(}=cn{t}_{)}$ 。

对于这个问题，一个号red字符串需要满足的条件是:

1. 对于任何前缀， $cn{t}_r\ge cn{t}_e\ge cn{t}_d$
2. 对于整个字符串， $cn{t}_r=cn{t}_e=cn{t}_d$ 。

因为前缀 $cn{t}_r\ge cn{t}_e$ 等价于后缀 $cn{t}_e\ge cn{t}_r$ ，第一个条件可拆为任何前缀 $cn{t}_e\ge cn{t}_d$ ，任何后缀 $cn{t}_e\ge cn{t}_r$ 。
我们可以从前往后遍历，当出现 $cn{t}_e<cn{t}_d$ 时，贪心地选取一个之前最迟出现的’?‘改为’e’(可以用栈实现)，后缀同理。
两次遍历完成后，贪心地完成第二个条件，从前往后根据所需数目将’?‘改为’r’,‘e’,‘d’。
然后检查是否为好red字符串即可。

参考代码

#include
using namespace std;

template<class T>inline void read(T&x){
	char c,last=' ';
	while(!isdigit(c=getchar()))last=c;
	x=c^48;
	while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+(c^48);
	if(last=='-')x=-x;
}

const int MAXN=3e5+5;
int stk[MAXN],top;//栈

string solve(string s){
	int n=s.length();
	s=" "+s;
	top=0;
	int c1=0,c2=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='?')stk[++top]=i;
		if(s[i]=='e')++c1;
		if(s[i]=='d')++c2;
		if(c1<c2){
			if(!top)return "NO";//找不到'?',不能填充'e'
			s[stk[top--]]='e';
			++c1;
		}
	}
	top=c1=c2=0;
	for(int i=n;i>=1;--i){
		if(s[i]=='?')stk[++top]=i;
		if(s[i]=='e')++c1;
		if(s[i]=='r')++c2;
		if(c1<c2){
			if(!top)return "NO";//找不到'?',不能填充'e'
			s[stk[top--]]='e';
			++c1;
		}
	}
	int c3=c1=c2=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='r')++c1;
		if(s[i]=='e')++c2;
		if(s[i]=='d')++c3;
	}
	for(int i=1;i<=n;++i){
		if(s[i]=='?'){//贪心完成第二个条件,按照'r','e','d'的顺序依次填防止匹配不上
			if(c1*3<n)s[i]='r',++c1;
			else if(c2*3<n)s[i]='e',++c2;
			else if(c3*3<n)s[i]='d',++c3;
		}
	}
	c1=c2=c3=0;
	for(int i=1;i<=n;++i){
		if(s[i]=='r')++c1;
		if(s[i]=='e')++c2;
		if(s[i]=='d')++c3;
		if(c1<c2||c2<c3)return "NO";//不满足第一个条件
	}
	if(c1!=c2||c2!=c3||c1!=c3){//不满足第二个条件
		return "NO";
	}
	return "YES";
}

int main()
{
	int T;read(T);
	while(T--){
		string s;
		cin>>s;
		cout<<solve(s)<<'\n';
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76