思路：栈stack
注：所有“编译错误”的字样都并非真正的编译错误，而是题目描述中输出ERR的情况。
定义一个栈 $s$，利用栈的位置：
问题转化
循环
因为时间复杂度忽略次要项，只保留最高次项，所以本题可转化为最深的循环有几层。
对于每个循环：
- 如果循环无法进入，则这层和它内部的循环均不计数，但要检查是否会出现编译错误。
- 如果循环执行常数次，则这层循环不计数。
- 如果循环执行 $n$ 次，则正常计数。
对于循环的起始值 $start$ 和终止值 $end$，考虑以下情况（$x,y$ 为常数，$ 1 \leq x \leq y \lt 100$）：
- $x,n$
- $n,x$
- $n,n$
- $x,y$
- $y,x$
- $x,x$
如果规定一个状态值 $state$：
| 循环状态 |
$state$ |
| 无法进入 |
$-1$ |
| 常数次 |
$0$ |
| $n$ 次 |
$1$ |
那么就有以下的对应：
| 循环起点和终点 |
$state$ |
| $x,n$ |
$1$ |
| $n,x$ |
$-1$ |
| $n,n$ |
$0$ |
| $x,y$ |
$0$ |
| $y,x$ |
$-1$ |
| $x,x$ |
$0$ |
所以，只需要根据 $start$ 和 $end$ 的关系，计算出 $state$ 即可。
变量记录
用 $vis$ 数组记录变量（字母）的使用情况，在进入循环时，对它的循环变量 $letter$ 进行 $vis[letter] = true$ 的赋值。
F-E合法判定
题目要求一个F必须和一个E配对。
遇到F时压栈，遇到E时弹栈。
如果弹栈时栈为空，不合法。
如果到最后栈中有残余，不合法。
数字比较
定义 $cmp(s_1,s_2)$ 函数进行比较，以下是返回值列表。
| 关系 |
返回值 |
| $s_1>s_2$ |
$-1$ |
| $s_1<s_2$ |
$1$ |
| $s_1=s_2$ |
$0$ |
朴素的字符串数字比较如下：
- 不同长度时，较长的数字为较大值。
- 相同长度时，从左往右找，先找到较大数位的是较大值。
- 否则，两数相等。
1
2
3
4
5
6
7
8
9
| int cmp(string s1, string s2) {
if(s1.length() > s2.length()) return -1;
if(s1.length() < s2.length()) return 1;
for(int i = 0; i < s1.length(); i++) {
if(s1[i] > s2[i]) return -1;
if(s1[i] < s2[i]) return 1;
}
return 0;
}
|
由于本题的特殊性，需要额外判断数字为 $n$ 的情况。
并且，$s_1<s_2$ 和 $s_1=s_2$ 对应的 $state$ 都为 $0$，所以将小于的情况当作等于处理。
所以，以下是适用本题的 $cmp()$ 函数。
1
2
3
4
5
6
7
8
9
10
11
12
| int cmp(string s1, string s2) {
if(s1 == s2) return 0;
if(s1 == "n") return -1;
if(s2 == "n") return 1;
if(s1.length() > s2.length()) return -1;
if(s1.length() < s2.length()) return 0;
for(int i = 0; i < s1.length(); i++) {
if(s1[i] > s2[i]) return -1;
if(s1[i] < s2[i]) return 0;
}
return 0;
}
|
所以，这个函数的返回值就是上述对应的 $state$。
循环的处理
使用node类型保存循环的信息，$depth$ 表示当前的循环深度。
1
2
3
4
5
| struct node {
int state;
char letter;
int depth;
};
|
使用 $curr_depth$ 记录当前的深度，如果 $state$ 不为 $-1$，就让 $curr_depth$ 加上 $state$。
否则，为了便于处理问题，认为：当外层循环的 $state$ 为 $-1$ 时，内层循环的 $state$ 也为 $-1$。
1
2
3
4
5
6
7
8
| if(x == -1) {
s.push({-1, letter, curr_depth});
} else if(s.size() && s.top().state == -1) {
s.push({-1, letter, curr_depth});
} else {
curr_depth += x;
s.push({x, letter, curr_depth});
}
|
在遇到E，弹出一个循环时，让 $max_depth$ 为 原来的 $max_depth$ 和 $curr_depth$ 中的较大值，同时取消标记 $letter$。
同样，如果会产生编译错误，让 $max_depth$ 的值为 $-1$。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| bool vis['z' + 10];
int my_max(int x, int y){
if(x == -1) return -1;
return max(x, y);
}
int main(){
node n = s.top();
s.pop();
vis[n.letter] = false;
max_depth = my_max(max_depth, n.depth);
if(n.state == 1) curr_depth -= 1;
}
|
由于可能产生编译错误，所以无论遇到F还是E，一旦 $max_depth$ 为 $-1$，只输入不计算，立刻跳出循环。
1
| if(max_depth == -1) continue;
|
注意：此处我使用的是边输入边计算，所以不能在检测到 $-1$ 后直接使用goto等方式跳出循环，否则一组数据就不能全部输入（但玄学的是能得63分）。
如果使用getline等方式提前输入数据，则可以放心使用goto直接跳出。
输出
本题输出的判断分为以下几步：
- 如果编译错误，直接输出
ERR。
- 否则，检查 $max_depth$ 是否和给定表达式中的指数相同。
表达式也有两种形式：
当 $max_depth=0$ 时，检查表达式是否为O(1)即可。
否则，进行字符串处理：
- 将 $max_depth$ 转换成字符串。
- 提取表达式中的指数部分：前四位舍去，后一位舍去。
- 检查是否相同。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void prn(string res, int depth){
if(depth == -1){
cout << "ERR" << endl;
return;
}
if(depth == 0){
if(res == "O(1)") cout << "Yes" << endl;
else cout << "No" << endl;
return;
}
if(to_string(depth) == res.substr(4, res.length() - 5)){
cout << "Yes" << endl;
return;
}else cout << "No" << endl;
}
|
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
|
#include <bits/stdc++.h>
#define set(x, y) memset(x, y, sizeof x)
using namespace std;
using ll = long long;
const int inf = 0x7f7f7f7f;
const int N = 110;
bool vis['z' + 10];
struct node {
int state;
char letter;
int depth;
};
stack<node> s;
void init() {
set(vis, 0);
s = stack<node>();
}
int cmp(string s1, string s2) {
if(s1 == s2) return 0;
if(s1 == "n") return -1;
if(s2 == "n") return 1;
if(s1.length() > s2.length()) return -1;
if(s1.length() < s2.length()) return 0;
for(int i = 0; i < s1.length(); i++) {
if(s1[i] > s2[i]) return -1;
if(s1[i] < s2[i]) return 0;
}
return 0;
}
void prn(string res, int depth){
if(depth == -1){
cout << "ERR" << endl;
return;
}
if(depth == 0){
if(res == "O(1)") cout << "Yes" << endl;
else cout << "No" << endl;
return;
}
if(to_string(depth) == res.substr(4, res.length() - 5)){
cout << "Yes" << endl;
return;
}else cout << "No" << endl;
}
int my_max(int x, int y){
if(x == -1) return -1;
return max(x, y);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("complexity.in", "r", stdin);
freopen("complexity.out", "w", stdout);
#endif
int T;
cin >> T;
int n;
string cplx;
while(T-- > 0) {
init();
cin >> n >> cplx;
char tag, letter;
string start, end;
int max_depth = 0, curr_depth = 0;
int x = 0;
for(int i = 1; i <= n; i++) {
cin >> tag;
switch(tag) {
case 'F':
cin >> letter;
cin >> start >> end;
if(max_depth == -1) continue;
x = cmp(start, end);
if(vis[letter]) {
max_depth = -1;
}
if(x == -1) {
s.push({-1, letter, curr_depth});
} else if(s.size() && s.top().state == -1) {
s.push({-1, letter, curr_depth});
} else {
curr_depth += x;
s.push({x, letter, curr_depth});
}
vis[letter] = true;
break;
case 'E':
if(s.empty()) {
max_depth = -1;
continue;
}
node n = s.top();
s.pop();
if(max_depth == -1) continue;
vis[n.letter] = false;
max_depth = my_max(max_depth, n.depth);
if(n.state == 1) curr_depth -= 1;
break;
}
}
if(s.size()) max_depth = -1;
prn(cplx, max_depth);
}
return 0;
}
|
补充
数组大小中的z
注意到以下语句：
'z' + 10是什么意思呢？
因为本题需要标记小写字母的使用情况，所以使用ASCII码最大的z再加上 $10$ 作为数组的大小，这样就可以直接使用char字符作为下标，而不用进行额外操作。