【题解】时间复杂度

题目戳我

( ext{Solution:})

显然模拟。

用栈来记录当前有多少循环没有匹配。并时刻用变量来更新当前复杂度指数。

注意如果出现编译错误，不能直接跳出，因为它没有读入完毕

对于不能进入的循环，其里面的时间复杂度是不需要计算的，只处理是不是编译错误即可。

其它的就是一些预处理，处理出当前字符串是不是可以算为(O(n))复杂度等等。

多用函数便于调试。

#include<bits/stdc++.h>
using namespace std;
namespace Hws{
	int T,L;
	string o,str;
	stack<int>t,tt;
	map<int,int>mp;
	vector<int>D;
	int Get(string x,int l){
		int s=0;
		for(int i=0;i<l;++i)
			if(isdigit(x[i]))
				s=s*10-'0'+x[i];
		return s;
	}
	bool check(string x){
		if(x[0]=='E'&&t.empty())return false;
		if(x[0]=='F'&&mp[x[2]]!=0)return false;
		return true;
	}
	int Getsta(string x,int len){
		if(x[len-1]=='n'&&x[4]!='n')return 1;
		return 2;
	}
	bool checkbreak(string x,int len){
		if(x[len-1]=='n')return false;
		if(x[4]=='n')return true;
		int s1=0,s2=0,p=4;
		while(isdigit(x[p])&&p<len){
			s1=s1*10-'0'+x[p];
			p++;
		}
		p++;
		while(p<len&&isdigit(x[p])){
			s2=s2*10-'0'+x[p];
			p++;
		}
		if(s1<=s2)return false;
		return true;
	}
	void del(){
		if(t.empty())return;
		int Tp=t.top();
		t.pop();
		mp[Tp]=0;
		int TT;
		if(!tt.empty())TT=tt.top();
		if(Tp==TT)tt.pop(); 
		if(!D.empty()&&Tp==D.back())D.pop_back();
		return;
	}
	int main(){
		scanf("%d",&T);
		while(T--){
			scanf("%d ",&L);
			o.clear();
			getline(cin,o);
			int len=o.size(),tm,A=0,fg=0;
			mp.clear();D.clear();
			while(!t.empty())t.pop();
			while(!tt.empty())tt.pop();
			tm=(len==4?0:Get(o,len));
			for(int i=1;i<=L;++i){
				str.clear();
				getline(cin,str);
				if(fg)continue;
				len=str.length();
				if(str[4]==str[6]&&str[4]=='n')str[4]=str[6]='1';
				if(!check(str)){
					puts("ERR");
					fg=1;continue;
				}
				if(str[0]=='E'){
					del();
					continue;
				}
				int sta=Getsta(str,len);
				t.push(str[2]);
				mp[str[2]]=i;
				if(checkbreak(str,len)){
					D.push_back(str[2]);
					continue;
				}
				if(sta==2||(int)D.size())continue;
				tt.push(str[2]); 
				A=max(A,(int)tt.size()); 
			}
			if(fg)continue;
			if(!t.empty())puts("ERR");
			else if(A==tm)puts("Yes");
			else puts("No");
		}
		return 0; 
	}
}
int main(){
	Hws::main();
	return 0;
}