#C241003A. [NOIP2017 提高组] 时间复杂度

标签（Label）

• 模拟

网址（Website）

P3952 [NOIP2017 提高组] 时间复杂度 - 洛谷

题解（Solution）

$\qquad$ 就提一句，所有的题在写代码的时候把所有的情况写到纸上或者是打到电脑上，依次枚举每一种情况，这样才能防止出错。

代码（Code）

#include<bits/stdc++.h>
#include<iostream>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define ull __int128
#define x first
#define y second
#define out() {flag = false;continue;}
inline int rd(){int x;return cin>>x,x;}
const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 105;
bool ST;

char s[N];
int L;


struct T{char ch;bool n,m;};
stack<T> st;
bitset<2024> exi;
int n,ans,f;
inline void solve(){
	while(st.size()) st.pop();
	exi.reset();
	ans = n = 0, f = 0;
	
	bool flag = true;
	cin>>L>>s;
	For(q,1,L){
		char opt, let, x[N], y[N];
		
		cin>>opt;
				
		if(opt=='F'){
			cin>>let>>x>>y;
			if(!flag) continue;
			
			if(exi[let] || let=='n') out();
			exi[let] = true;
			if((x[0]=='n'&&y[0]!='n') || (y[0]!='n' && atoi(x)>atoi(y))){
				st.push({let,1,0});
				f++;
			}else			
			if(x[0]!='n' && y[0]=='n' && !f){
				st.push({let,0,1});
				ans = max(ans, ++n);
			}else{
				st.push({let,0,0});
			}			
		}
		
		
		if(opt=='E'){
			if(st.empty()) out();
			
			if(!flag) continue;
			
			exi[st.top().ch] = false;
			
			if(st.top().n) f--;
			
			if(st.top().m) n--;
			
			st.pop();
		}
	}
	
	if(st.size() || !flag) return cout<<"ERR\n",void();
	
	if(s[2]=='1'){//O(1)
		cout<<(ans==0 ? "Yes\n" : "No\n");
	}else 
	if(s[5]==')'){
		int x = atoi(s+4);
		cout<<(ans==x ? "Yes\n" : "No\n");
	}else{
		int x = atoi(s+4);
		cout<<(ans==x ? "Yes\n" : "No\n");
	}
}

bool ED;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
	int T = rd(), Tim = clock();
	while(T--) solve();
	return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}