题目链接

蒟蒻调了三个小时的代码终于把这题AC了qwq。

这题值得注意的几个点有:

  1. E也有可能有多余导致ERR
  2. 每遇到一个E都必须清理到前一个F语句的变量名。

另外:

  1. sscanf可以很方便的格式化字符串到另一个要存储的数据里面去。
  2. 程序输入的每行代码可以使用结构体保存,而一段程序可以使用队列,但是STL提供的队列好像不能满足我们的要求,于是我们选择vector
  3. 判断是否每个F都可以对上一个E使用栈可以很方便的解决。

剩下的慢慢调试就好了qwq。

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
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;

//#define DEBUG

int T;

struct Line {
char op, i;
int x, y;
bool disable;
};

int main() {
#ifdef DEBUG
freopen("P3952.in", "r", stdin);
#endif

cin >> T;
while (T--) {
int L, reqO = 0, resO = 0;
string O;
cin >> L >> O;
if (O != "O(1)")
sscanf(O.c_str(), "O(n^%d)", &reqO);

vector<Line> que;
for (int i = 1; i <= L; i++) {
char op;
cin >> op;
if (op == 'F') {
char i;
string tmp1, tmp2;
cin >> i >> tmp1 >> tmp2;
int x = (tmp1 == "n" ? 101 : stoi(tmp1));
int y = (tmp2 == "n" ? 101 : stoi(tmp2));
que.push_back(Line{'F', i, x, y, 0});
} else if (op == 'E') {
que.push_back(Line{'E', 0, 0, 0, 0});
}
}

int err = 0, tmpO = 0;
map<char, bool> var;
stack<char> op;
Line nowLine, lastLine = {'F', 0, 0, 101, 0};
for (auto k = que.begin(); k != que.end(); k++) {
nowLine = *k;

if (nowLine.op == 'F') {
op.push('F');

if (!var[nowLine.i]) var[nowLine.i] = 1;
else { err = 1; break; }

if (!nowLine.disable) {
if (nowLine.x <= nowLine.y) {
if (nowLine.y == 101 && nowLine.x != 101) {
stack<char> st;
st.push('F');
auto p = k + 1;
tmpO++;
while (!st.empty() && p != que.end()) {
if (p->op == 'E') {
resO = max(resO, tmpO);
st.pop();
tmpO--;
} else {
st.push('F');
if (p->x > p->y) break;
if (p->y == 101 && p->x != 101) tmpO++;
p->disable = 1;
}
p++;
}

resO = max(resO, tmpO);
tmpO = 0;
}
} else {
nowLine.disable = 1;
stack<char> st;
st.push('F');
for (auto p = k; p != que.end(); p++) {
if (st.empty()) break;
if (p->op == 'F') {
st.push('F');
p->disable = 1;
} else if (st.top() == 'F') {
st.pop();
}
}
}
}
} else {
if (op.empty()) { err = 1; break; }
if (op.top() == 'F') op.pop();
for (auto p = k; p >= que.begin(); p--) {
if (p->op == 'F' && var[p->i]) var[p->i] = 0;
}
}

lastLine = nowLine;
}

if (err || !op.empty()) {
cout << "ERR" << endl;
} else if (resO == reqO) {
cout << "Yes" << endl;
} else {
#ifdef DEBUG
cout << "No: " << resO << endl;
#else
cout << "No" << endl;
#endif
}
}

return 0;
}

评论