【25杭电春季营热身赛】 T1006 对吗？对的对的 不对不对

Problem Description

CF (Card Fight) 是一款经典的卡牌战斗游戏，拥有丰富的卡牌和五花八门的机制。

小D作为一个游戏主播在直播CF时遇到了一个难题，进行了以下的思考：

“😵哦不对，我打错了！🤓✋哦对的对的，🤨哦不对，😫啊我跟你们说不对，哎呀不对‍，🤔哦对的对的对的对…对吗？哦对的对的对的😁，😐😨不对吧，啊我都搞晕掉了😵‍💫哦😲对对对对对，对对对对我明白了🤓…”

由于脑子过载，小D经历了千般转折，但是熟知他的观众都早已经了解他的思考方式了：

  • 小D说的话经过录播记录变成由大写字母组成的字符串。
  • 如果子序列的YES比NO多，小D就会说 “DUI DE”（对的）
  • 如果子序列的NO比YES多，小D就会说 “BUDUI BUDUI”（不对不对）
  • 如果子序列的YES和NO一样多，小D就会说 “DUI DUI DUIMA”（对 对 对吗？）

但是小D经常再三思考，他会尝试修改原来记录中的任意一个字符以尽可能改变原来的答案，如果改变成功了，他就会恍然大悟，附带一句 “O”（哦！），来表达他的惊讶之情：

  • 原来是 “DUI DE”，他思考后能变成不对就会恍然大悟，最后说出”O BUDUI BUDUI”
  • 原来是 “BUDUI BUDUI”，他思考后能变成对的也会恍然大悟，最后说出”O DUI DE”
  • 如果原来就是一样多，他就会说出”DUI DUI DUIMA”
  • 如果没有改变或者最多变成一样多，他就会说出原来的答案

你可以预测出小D要说的下一句话吗？

Input

每个测试包含多个测试用例。第一行包含测试用例的数量 $t \ (0≤t≤100)$。测试用例说明如下。

每个测试用例由一行字符串 $S$ $(|S|≤10^5)$组成，代表小D说过的话。

保证所有测试用例中 $|S|$ 的总和不超过 $2×10^6$。

Output

对于每个测试用例，输出两行

第一行由两个数字组成由空格分开，表示原来字符串中YES的子序列数量和NO的子序列数量。

第二行是一个字符串，表示小D接下来会说的话。

Sample Input

1
2
3
4
3 
YES
YYEESSNOOO 
ABULAIKESIYESNO

Sample Output

1
2
3
4
5
6
1 0 
DUI DE 
8 3 
O BUDUI BUDUI 
1 1 
DUI DUI DUIMA

题解

在刘春英老师发的题解上进行补充。

子序列问题，考虑dp。例如我们求字符串当中YES的数量。我们定义pre_yes[i]为在i前面有多少个yes的数量。pre_ye[i] pre_y[i]同理。那么我们就可以得出递推式pre_yes[i] = pre_yes[i - 1] + (s[i] == 'S') * pre_ye[i - 1]（其他同理）。题目中的第一问就是输出pre_yes[len]和pre_no[len]。

第二问，我们可以遍历字符串去计算修改这个字母对于YES和NO个数的贡献。当YES的数量小于NO的数量时，我们肯定是贪心的把每个字符修改成Y或者E或者S，怎么计算呢？举个例子，假设遍历到的字母是Y，我们首先先要减去这个Y对于YES子序列的贡献，这个贡献就是suf_es[i]，然后再加上E或者S做出贡献的最大值。算E做出贡献的时候，肯定是算前面有多少个Y，后面有多少个S，两者再相乘，注意在算的时候是(pre_y[i] - 1) * (suf_s[i]) ，减去1是因为当前字母本身就是Y。剩下11种情况基本同理。

代码

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#define int long long
const int N = 2e5 + 50;
int pre_y[N], pre_ye[N], pre_yes[N];
int pre_n[N], pre_no[N];
int suf_es[N], suf_s[N];
int pre[30][N], suf[30][N];
void solve()
{
	int len, cnty = 0, cntn = 0;
	string s;
	cin >> s;
	len = s.length();
	s = " " + s;
	for (int i = 0; i <= len + 1; ++i)
	{
		pre_y[i] = pre_ye[i] = pre_yes[i] = 0;
		pre_n[i] = pre_no[i] = 0;
		suf_es[i] = suf_s[i] = 0;
		for (char j = 'A'; j <= 'Z'; ++j)
			pre[j - 'A'][i] = suf[j - 'A'][i] = 0;
	}

	for (int i = 1; i <= len; ++i)//前缀
	{
		pre_y[i] = pre_y[i - 1] + (s[i] == 'Y');
		pre_ye[i] = pre_ye[i - 1] + (s[i] == 'E') * pre_y[i - 1];
		pre_yes[i] = pre_yes[i - 1] + (s[i] == 'S') * pre_ye[i - 1];
		pre_n[i] = pre_n[i - 1] + (s[i] == 'N');
		pre_no[i] = pre_no[i - 1] + (s[i] == 'O') * pre_n[i - 1];

		pre[s[i] - 'A'][i]++;
		for (char j = 'A'; j <= 'Z'; ++j)
			pre[j - 'A'][i] += pre[j - 'A'][i - 1];
	}
	for (int i = len; i >= 1; --i)//后缀
	{
		suf_s[i] = suf_s[i + 1] + (s[i] == 'S');
		suf_es[i] = suf_es[i + 1] + (s[i] == 'E') * suf_s[i + 1];

		suf[s[i] - 'A'][i]++;
		for (char j = 'A'; j <= 'Z'; ++j)
			suf[j - 'A'][i] += suf[j - 'A'][i + 1];
	}

	cnty = pre_yes[len], cntn = pre_no[len];
	cout << pre_yes[len] << " " << pre_no[len] << endl;
	if (pre_yes[len] > pre_no[len])
	{
		for (int i = 1; i <= len; ++i)
		{
			int cony = 0, conn = 0;
			if (s[i] == 'Y')
			{
				cony = suf_es[i];
				conn = max(suf['O' - 'A'][i], pre['N' - 'A'][i]); // N O
			}
			else if (s[i] == 'E')
			{
				cony = pre_y[i] * suf_s[i];
				conn = max(suf['O' - 'A'][i], pre['N' - 'A'][i]); // N O
			}
			else if (s[i] == 'S')
			{
				cony = pre_ye[i];
				conn = max(suf['O' - 'A'][i], pre['N' - 'A'][i]); // N O
			}
			else if (s[i] == 'N')
			{
				conn -= suf['O' - 'A'][i];
				conn += pre['N' - 'A'][i] - 1;
			}
			else if (s[i] == 'O')
			{
				conn -= pre['N' - 'A'][i];
				conn += suf['O' - 'A'][i] - 1;
			}
			else
				conn = max(pre['N' - 'A'][i], suf['O' - 'A'][i]);
			if (cnty - cony < cntn + conn)
			{
				cout << "O BUDUI BUDUI" << endl;
				return;
			}
		}
		cout << "DUI DE" << endl;
	}
	else if (pre_yes[len] < pre_no[len])
	{
		for (int i = 1; i <= len; ++i)
		{
			int cony = 0, conn = 0;
			if (s[i] == 'Y')
			{
				cony -= suf_es[i];
				cony += max((pre_y[i] - 1) * (suf_s[i]), pre_ye[i - 1]); // E S
			}
			else if (s[i] == 'E')
			{
				cony -= pre_y[i] * suf_s[i];
				cony += max(suf_es[i + 1], pre_ye[i - 1]); // Y S
			}
			else if (s[i] == 'S')
			{
				cony -= pre_ye[i];
				cony += max(suf_es[i + 1], (pre_y[i]) * (suf_s[i] - 1)); // Y E
			}
			else if (s[i] == 'N')
			{
				cony = max({suf_es[i], pre_y[i] * suf_s[i], pre_ye[i]});
				conn = suf['O' - 'A'][i];
			}
			else if (s[i] == 'O')
			{
				cony = max({suf_es[i], pre_y[i] * suf_s[i], pre_ye[i]});
				conn = suf['N' - 'A'][i];
			}
			else
				cony = max({suf_es[i], pre_y[i] * suf_s[i], pre_ye[i]});
			if (cnty + cony > cntn - conn)
			{
				cout << "O DUI DE" << endl;
				return;
			}
		}
		cout << "BUDUI BUDUI" << endl;
	}
	else
		cout << "DUI DUI DUIMA" << endl;
}
【25杭电春季营热身赛】 T1006 对吗？对的对的 不对不对
http://example.com/2025/03/01/problem1/
作者
LuminousYT
发布于
2025年3月1日
许可协议