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

原题链接

链接

题目大意

定义由若干不相交的 $red$ 序列构成的字符串为好的 $red$ 字符串。
$example：$
$rerded$ 是好的；
$redrde$ 不是好的。
给定由’r’,‘e’,‘d’,?‘构成的字符串，’?'能任意替换成任何字符，求能否使得字符串为好的 $red$ 字符串。

题解

这题看着很像由三个分支的括号匹配，所以我们同样用栈来解决，
对于一个已经优秀的字符串，在任何位置上，已经出现的’r’总比已经出现的’e’次数多，‘e’总比’d’多，而未出现的恰好相反 $|r|\le |e|\le |d|$。
考虑用前后缀记录当前的位置是否符合要求，
对于前缀我们维护 $|d|\le |e|$ ，
对于前缀我们维护 $|r|\le |e|$ ，
等价于前缀和后缀的所有条件，
其中若已经有错误，就尽可能修改，用栈维护可以更改的值，
考虑包含’?‘的字符串，尽可能加入一个能让它符合的字母，
最后，使得每一个’r’,‘e’,'d’都能相互匹配，我们判断一下 $|r|=|e|=|e|=a/3$。

参考代码

#include
using namespace std;
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)             //维护'e''d'，优先填入
	{
		if(s[i]=='?')stk[++top]=i;
		if(s[i]=='e')++c1;
		if(s[i]=='d')++c2;
		if(c1<c2){
			if(!top)return "NO";
			s[stk[top--]]='e';
			++c1;
		}
	}
	top=c1=c2=0;
	for(int i=n;i>=1;--i)         //维护'e''r'，优先填入
	{
		if(s[i]=='?')stk[++top]=i;
		if(s[i]=='e')++c1;
		if(s[i]=='r')++c2;
		if(c1<c2)
		{
			if(!top)return "NO";
			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]=='?')
		{
			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;
	cin>>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
77
78
79