[NOIP2017 提高组] 时间复杂度
题目背景
NOIP2017 提高组 D1T2
题目描述
小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序， 于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。
A++语言的循环结构如下：
F i x y
循环体
E
其中F i x y表示新建变量 \(i\)（变量 \(i\) 不可与未被销毁的变量重名）并初始化为 \(x\)， 然后判断 \(i\) 和 \(y\) 的大小关系，若 \(i\) 小于等于 \(y\) 则进入循环，否则不进入。每次循环结束后 \(i\) 都会被修改成 \(i +1\)，一旦 \(i\) 大于 \(y\) 终止循环。
\(x\) 和 \(y\) 可以是正整数（\(x\) 和 \(y\) 的大小关系不定）或变量 \(n\)。\(n\) 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 \(100\)。
E 表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。
注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 \(\operatorname O\) 表示通常意义下 \(Θ\) 的概念。
输入格式
输入文件第一行一个正整数 \(t\)，表示有 \(t\)（\(t \le 10\)）个程序需要计算时间复杂度。 每个程序我们只需抽取其中 F i x y 和 E 即可计算时间复杂度。注意：循环结构允许嵌套。
接下来每个程序的第一行包含一个正整数 \(L\) 和一个字符串，\(L\) 代表程序行数，字符串表示这个程序的复杂度，O(1) 表示常数复杂度，O(n^w) 表示复杂度为 \(n^w\)，其中 \(w\) 是一个小于 \(100\) 的正整数，输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。
接下来 \(L\) 行代表程序中循环结构中的F i x y或者 E。 程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y， 其中 \(i\) 是一个小写字母（保证不为\(n\)），表示新建的变量名，\(x\) 和 \(y\) 可能是正整数或 \(n\) ，已知若为正整数则一定小于 \(100\)。
程序行若以E开头，则表示循环体结束。
输出格式
输出文件共 \(t\) 行，对应输入的 \(t\) 个程序，每行输出 Yes 或 No 或者 ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出 No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出 ERR。
注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。
样例 #1
样例输入 #1
8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E
样例输出 #1
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
样例 #2
样例输入 #2
9
22 O(n^7)
F a 70 94
F b 90 94
E
E
F a 29 n
F b 22 n
F c 4 27
F d 85 n
F e 24 n
F f 56 87
F g 19 66
F h 6 41
F i 78 92
F j 7 n
E
E
E
E
E
E
E
E
66 O(n^8)
F a 87 n
F b 70 n
F c 65 n
F d 85 n
F e 35 n
E
E
E
E
E
F a 33 59
F b 74 n
F c 3 n
F d 81 88
F e 82 97
F f 87 98
F g 49 88
F h 72 98
F i 56 n
F j 48 76
F k 90 n
F l 54 n
F m 86 n
E
E
E
E
E
E
E
E
E
E
E
E
E
F a 32 46
F b 56 n
F c 5 n
F d 65 75
F e 4 n
F f 78 n
F g 75 n
F h 82 n
F i 52 n
F j 53 n
E
E
E
E
E
E
E
E
E
E
E
E
F a 3 n
F b 6 n
F c 22 n
F d 42 n
E
E
E
E
60 O(n^11)
F a 46 n
F b 3 64
F c 8 n
F d 19 n
F e 30 n
F f 22 16
F g 40 n
F h 10 n
F i 25 n
F a 62 n
E
E
E
E
E
E
E
E
E
E
F a 81 n
F b 37 n
F c 44 n
F d 13 n
F e 56 94
E
E
E
E
E
F a 50 n
F b 75 n
F c 3 74
F d 58 n
F e 15 n
F f 43 n
F g 32 n
F h 25 35
F i 47 n
F j 56 n
F k 53 81
F l 63 n
F m 78 87
F o 73 n
F p 90 n
E
E
E
E
E
E
E
E
E
E
E
E
E
E
E
36 O(n^7)
F a 68 n
F b 42 n
F c 16 n
F d 26 89
E
E
E
E
F a 7 44
F b 13 60
F c 85 97
F d 38 74
F e 73 n
F f 65 83
F g 52 n
F h 3 5
F i 88 n
F j 24 n
F k 81 n
F l 1 n
F m 85 n
E
E
E
E
E
E
E
E
E
E
E
E
E
F a 36 67
E
84 O(n^11)
F a 85 86
F b 76 90
F c 45 75
F d 41 43
F e 87 96
F f 18 n
F g 15 76
F h 47 n
E
E
E
E
E
E
E
E
F a 61 n
F b 62 n
F c 3 32
F d 4 n
F e 18 n
F f 53 74
F g 64 n
F h 87 n
F i 77 n
F j 60 69
F k 67 96
F l 34 n
F m 62 n
E
E
E
E
E
E
E
E
E
E
E
E
E
F a 74 n
F b 17 n
F c 9 n
F d 43 n
F e 82 n
F f 57 65
F g 35 n
F h 29 n
F i 37 95
E
E
E
E
E
E
E
E
E
F a 31 n
F b 14 71
F c 74 n
F d 81 n
F e 8 n
F f 11 n
F g 29 n
F h 19 n
F i 60 n
F j 68 79
F k 63 n
F l 11 n
E
E
E
E
E
E
E
E
E
E
E
E
62 O(n^10)
F a 26 n
F b 84 n
F c 69 73
F d 59 n
F e 13 n
E
E
E
E
E
F a 46 n
F b 61 n
F c 47 n
F d 43 n
F e 77 n
F f 33 n
F g 32 n
F h 71 n
F i n n
F j 35 n
F k 47 86
F l 53 n
E
E
E
E
E
E
E
E
E
E
E
E
F a 31 38
F b 74 95
F c 6 66
F d 68 84
F e 72 n
F f 1 n
F g 47 89
F h 89 n
F i 5 n
F j 34 n
F k 2 n
F l 27 n
E
E
E
E
E
E
E
E
E
E
E
E
F a 33 58
F b 5 70
E
E
34 O(n^4)
F a 50 n
F b 6 78
F c 9 10
F d 6 n
F e 17 n
F f 24 n
E
E
E
E
E
E
F a 50 56
F b 2 17
F c 57 n
F d 46 86
F e 38 60
F f 56 n
F g 77 94
F h 26 71
F i 59 n
F j 22 40
F k 13 n
E
E
E
E
E
E
E
E
E
E
E
56 O(n^5)
F a 9 n
F b 64 n
F c 17 n
F d n 6
F e 59 n
F f 36 n
F g 48 64
F h 17 n
E
E
E
E
E
E
E
E
F a 20 n
F b 19 n
F c 18 55
F d 46 n
F e 58 70
F f 12 46
E
E
E
E
E
E
F a 20 n
F b 35 n
F c 44 67
F d 40 49
F e 71 75
F f 61 n
F g 76 n
F h 3 n
F i 99 60
F j 59 80
F k 27 n
F l 30 n
F m 5 n
F o 86 n
E
E
E
E
E
E
E
E
E
E
E
E
E
E
2 O(n^1)
F a n n
E
样例输出 #2
ERR
ERR
ERR
Yes
No
Yes
Yes
Yes
No
样例 #3
样例输入 #3
2
54 O(n^9)
F a 8 n
F b 60 62
F c 20 n
F d 81 n
F e 70 n
F f 78 n
E
E
E
E
E
E
F a 76 n
F b 34 n
F c 16 n
F d 2 n
F e 5 n
F f 87 n
F g 8 n
F h 3 n
F i n 17
E
E
E
E
E
E
E
E
E
F a 90 n
F b 79 n
F c 24 n
F d 58 n
F e 58 n
F f 61 32
F g 5 n
F h 80 n
F i 54 n
F j 5 n
F k 79 97
F l 61 86
E
E
E
E
E
E
E
E
E
E
E
E
42 O(n^4)
F a 38 n
F b 7 n
F c n n
F d 79 n
F e 20 n
F f 99 7
F g 68 n
F h 74 n
F i 24 n
E
E
E
E
E
E
E
E
E
F a 10 n
F b 65 n
F c 45 91
F d n 7
F e 44 n
E
E
E
E
E
F a 75 n
F b 55 n
F c 82 39
F d 59 n
F e 38 n
F f 36 50
F g 40 n
E
E
E
E
E
E
E
样例输出 #3
No
Yes
提示
【输入输出样例解释 \(1\)】
第一个程序 \(i\) 从 \(1\) 到 \(1\) 是常数复杂度。
第二个程序 \(x\) 从 \(1\) 到 \(n\) 是 \(n\) 的一次方的复杂度。
第三个程序有一个 F 开启循环却没有 E 结束，语法错误。
第四个程序二重循环，\(n\) 的平方的复杂度。
第五个程序两个一重循环，\(n\) 的一次方的复杂度。
第六个程序第一重循环正常，但第二重循环开始即终止（因为 \(n\) 远大于 \(100\)，\(100\) 大于 \(4\)）。
第七个程序第一重循环无法进入，故为常数复杂度。
第八个程序第二重循环中的变量 \(x\) 与第一重循环中的变量重复，出现语法错误②，输出 ERR。
【数据规模与约定】
对于 \(30\%\) 的数据：不存在语法错误，数据保证小明给出的每个程序的前 \(L/2\) 行一定为以 F 开头的语句，第 \(L/2+1\) 行至第 \(L\) 行一定为以 E 开头的语句，\(L \le 10\)，若 \(x\)、\(y\) 均为整数，\(x\) 一定小于 \(y\)，且只有 \(y\) 有可能为 \(n\)。
对于 \(50\%\) 的数据：不存在语法错误，\(L \le 100\)，且若 \(x\)、\(y\) 均为整数，\(x\) 一定小于 \(y\)， 且只有 \(y\) 有可能为 \(n\)。
对于 \(70\%\) 的数据：不存在语法错误，\(L \le 100\)。
对于 \(100\%\) 的数据：\(L \le 100\)。
题解
易错点
- 判断x y大小，方便知道循环能否进行下去
- 若check（a，b） = 0 则说明为两个常数，且一大一小或相等
若check（a，b） = 1 则说明为a为常数，b为 “ n ”， 时间复杂度为O（n）
若check（a，b） = -1则说明a > b, 无法进入循环，影响后继循环判断 - 生成两个栈stack1， stack2。
stack1存时间复杂度（-1， 0， 1）
stack2存变量，方便在退出一个循环就，删除一个变量名 - 创建一个set
st，用于存变量名，防止在嵌套循环中出现变量名冲突 - ERR：字符 “ F ” 和 “ E ” 出现的次数不一致，或变量名重复
代码c++
#include <bits/stdc++.h>
#define SZ(v) ((int)v.size())
typedef long long ll;
using namespace std;
int _;
int l;
string s, a, b, c, d;
bool comparea(string a, string b) {
if(SZ(a) < SZ(b)) {
return true;
}
else if(SZ(a) > SZ(b)) {
return false;
}
else {
for(int i = 0; i < SZ(a); i++) {
if(a[i] < b[i]) return true;
if(a[i] == b[i]) continue;
if(a[i] > b[i]) return false;
}
}
return true;
}
int check(string a, string b) {
if(a != "n" && b == "n") return 1;
else if(a == "n" && b != "n") return -1;
else if(a != "n" && b != "n") {
if(comparea(a, b)) return 0;
else return -1;
}
return 0;
}
void solve() {
cin >> l >> s;
set<string> st;
stack<string> sta2;
stack<int> sta;
st.clear();
int sum = 0, ans = 0;
bool flag = false;
for(int i = 0; i < l; i++) {
cin >> a;
if(a == "F") {
cin >> b >> c >> d;
if(st.count(b) != 0) {
flag = true;
}
else {
st.insert(b);
}
int x = check(c, d);
if((sta.size() == 0 || sta.top() != -1) && x != -1) sum += x;
if(sta.size() > 0 && sta.top() == -1) sta.push(-1);
else sta.push(x);
sta2.push(b);
}
else {
if(sta.size() > 0) {
if(sta.top() == 1) sum -= sta.top();
sta.pop();
st.erase(sta2.top());
sta2.pop();
}
else {
flag = true;
}
}
ans = max(ans, sum);
}
if(flag || sta.size() != 0) {
cout << "ERR\n";
}
else {
string tmp = "";
if(ans == 0) tmp = "O(1)";
else tmp = "O(n^" + to_string(ans) + ")";
// cout << "tmp = " << tmp << "\n";
// cout << "ans = " << ans << "\n";
if(tmp == s) {
cout << "Yes\n";
}
else {
cout << "No\n";
}
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
// freopen("in.in", "r", stdin);
// freopen("out.out", "w",stdout);
cin >> _;
while(_--) solve();
return 0;
}