P3952-时间复杂度

题目链接

题目描述

小明正在学习一种新的编程语言 A++,刚学会循环语句的他激动地写了好多程序并 给出了他自己算出的时间复杂度,可他的编程老师实在不想一个一个检查小明的程序, 于是你的机会来啦!下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

原题请至luogu查看

题解

代码如下:

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
#include<bits/stdc++.h>

using namespace std;

string a, b;
int c, d, e, f[27], g[27], h, k, l[100], m, n, o, T;

//c是有几个句子,d是题目给的复杂度是多少

//e是当前在几重循环,f[]是判断变量是否使用过

//g[]是存下每个循环的变量,h是当前复杂度是多少(与e不同)

//k是判断下面程序是否进行,l[]是存下哪几个循环加了复杂度

//m是当前最大复杂度,n是存下k=1时的循环数

//T是数据组数

void init()//初始化 很重要

{
c = 0; d = 0; m = 0; n = 0; e = 0; h = 0; k = 0;
memset(f, 0, sizeof(f));
memset(l, 0, sizeof(l));
}

int main()
{
scanf("%d", &T);

while (T--)
{
init();
do {
a = b, cin >> b;
} while (b[0] != 'O');

int len_a = a.length();
int len_b = b.length();

for (int i = 0; i < len_a; i++)
c = c * 10 + a[i] - 48;
for (int i = 4; i < len_b - 1; i++)
d = d * 10 + b[i] - 48; //取出题目给的时间复杂度 O(1)不影响

while (c > 0)
{
c--;
cin >> a;//读入F 或 E ,句子数-1
if (a[0] == 'F')
{
e++; cin >> a;
if (f[a[0] - 96]) e = -1;//如果被用过,标记ERR

else //反之存起来并标记

f[a[0] - 96] = 1, g[e] = a[0] - 96;
cin >> a >> b;
if (a[0] != 'n'&&b[0] == 'n'&&k == 0)
h++, l[e] = 1;//如果a是数字,b是n,而且可以运行,那么当前复杂度+1
else
if (((a.length() == b.length() && a > b) || (a.length() > b.length()) || (a[0] == 'n'&&b[0] != 'n')) && k == 0) k = 1, n = e;

}
else//如果是E

{
m = max(m, h); f[g[e]] = 0; //将最大复杂度更改 ,变量标记没用过
if (l[e] == 1) h--, l[e] = 0;
e--;
if (n > 0 && e < n)
k = 0, n = 0; //如果当前循环加了复杂度,当前复杂度-1,标记清空

}
if (e == -1) printf("ERR\n"), c = -1;

}
//处理结果

if (e > 0) printf("ERR\n");
if (e == 0 && m == d) printf("Yes\n");
if (e == 0 && m != d) printf("No\n");
}

return 0;
}

~

-------------本文结束,感谢您的阅读-------------