Burnling's Blog
0%

P3952 时间复杂度

发表于 更新于 分类于 ，

题面：P3952 [NOIP2017 提高组] 时间复杂度

这个世界上为什么会有模拟这种东西啊

因为做的时候没审好题导致心态直接爆炸

以为会出现

1
2
3
4
5
6
F i 1 n
F a 1 i
F b a n
E
E
E

这种东西

后来再读题发现边界字母只会出现 $n$

感谢出题人不杀之恩

题解

首先考虑什么情况下会出现 ERR

  1. 出现了使用过的变量

    可以开一个 map<char,bool> 来记录这个变量是否使用过

  2. F 和 E 不匹配

    用栈来模拟，如果 E 的时候栈为空或者程序结束后栈不为空则不合法

接着开始计算复杂度

一共有四种情况

  1. 从 常量 到 常量 ：常数复杂度，比较两个常量 $a_1,a_2$的大小即可，若 $a_1\leq a_2$ ，那么可以累加，否则不能进入循环
  2. 从 常量 到 $n$ ：由于常量值小于 $100$ 而 $n$ 远大于 $100$ ，可以累加 $O(N)$ 的复杂度
  3. 从 $n$ 到 常量 ： 无法进入循环
  4. 从 $n$ 到 $n$ ：常数复杂度

其中，仅有 $O(N)$ 复杂度可以累加

对于不能进入循环的情况，不能简单地跳过，因为中间可能会出现 ERR

那么可以用栈来记录该循环体内部是否可以记录复杂度

又因为之前正好也需要一个栈来记录循环嵌套情况（仅通过栈内元素数量判断）

那么就可以将这个栈定义为 stack<bool> ，若栈顶为 true 则表示不能累加复杂度，向栈内 push 一个 true （保证内部循环也不累加复杂度）就可以继续了

另外，一层循环退出后要及时删除该层循环所使用的变量，这里用 stack<char> 来记录当前层循环的变量名

一个程序的复杂度是最深的循环层数，所以还要取 $\max$

代码

愿天堂没有模拟

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

const int maxL = 200;

stack<bool> blc;//以后的循环加不加复杂度
stack<char> tp;//目前循环的变量名（删变量时用）
map<char,bool> vis;//判断变量是否用过

int T;
int L;
char Tc[maxL];//小明给出的时间复杂度
char opt_;//操作符，F或者E
bool flg1;//判断是否ERR
char bl,ff[maxL],tt[maxL];
int fzd;//记录当前复杂度

//多组数据，记得初始化
inline void INIT(){
	for(int i = 'a';i<='z';i++) vis[i] = 0;
	fzd = 0;
	while(!blc.empty()) blc.pop();
	while(!tp.empty()) tp.pop();
	memset(Tc,0,sizeof(Tc));
	flg1 = false;
}

//将char数组转为数字，用于提取循环边界的数字
inline int ToInt(char S[]){
	int res = 0;
	int pd = 1;
	int Ll = strlen(S);
	for(int i = 0;i<Ll;i++){
		res += (S[Ll-i-1] - '0') * pd;
		pd *= 10;
	}
	return res;
}

//判断能否累加复杂度（如果栈空或者栈顶为false则可以累加）
//写麻烦了，其实可以 return blc.empty() || !blc.top() 的
inline bool gtc(){
	return !(!blc.empty() && blc.top());
}

//从小明给出的复杂度中提取O(N^x)的x
inline int gtC(char S[]){
	int cnt = 0;
	int Ll = strlen(S);
	char C[maxL];
	bool nt1 = false;
	for(int i = 0;i<Ll;i++){
		if(S[i] == 'n') nt1 = true;//如果出现了n，那么不是O(1) 复杂度
		if(isdigit(S[i])) C[cnt++] = S[i];
	}
	C[cnt] = '\0';
	return nt1 ? ToInt(C) : 0;
}

int main(){
//	freopen("P3952_6.in","r",stdin);
//	freopen("out.txt","w",stdout);
	scanf("%d",&T);
	while(T--){
		INIT();
		scanf("%d %s",&L,Tc);
		int maf = 0;
		for(int i = 1;i<=L;i++){
			scanf("\n%c",&opt_);
			if(opt_ == 'F'){
				scanf(" %c%s%s",&bl,ff,tt);//这个读入真的要好小心才不会错
				if(vis[bl]) flg1 = true; //变量重复，ERR（但因为多组数据，只能接着读入程序）
				tp.push(bl);//记录当前层循环用的变量名
				vis[bl] = 1;//记录该变量名已经使用
                
				if(!gtc()){
					blc.push(true);//如果当前层循环不能累加复杂度，那么其内部的循环也不能累加
					continue;
				}
				if(ff[0] == 'n'){
					if(tt[0] == 'n'){
						//F n to n 常数复杂度，不累加
						blc.push(false);
					}else{
						//F n to C 无法进入循环
						blc.push(true);
					}
				}else{
					if(tt[0] == 'n'){
						//F C to n O(N)复杂度
						if(gtc())fzd++;//如果可以累加就累加
						maf = max(maf,fzd);//求最大复杂度
						blc.push(false);
					}else{
						//F C to C 常数复杂度/无法进入循环
						int t1 = ToInt(ff);
						int t2 = ToInt(tt);
						blc.push(t1 > t2);
					}
				}
			}else{
				if(blc.empty()){
					flg1 = true;//栈空却需要退出循环，ERR
					continue;
				}else{
					blc.pop();
					char c = tp.top();tp.pop();//删除变量名
					vis[c] = 0;
					fzd--;//退出循环后复杂度变小
					fzd = max(fzd,0);
				}
			}
		}
		if(flg1 || !blc.empty()){
			printf("ERR\n");
			continue;
		}else{
			int r1,r2;
			r1 = gtC(Tc);
			r2 = max(maf,fzd);
			printf("%s\n",r1 == r2 ? "Yes" : "No");
		}
	}
	return 0;
}