看了下题解，发现思路和其他题解大佬们的都不一样啊

本题是一个简单的模拟题。

需要注意的几个问题：

1.for 循环里面 n在右边才能算

是不是感觉很玄学啊，然而的确是这样的，如果n在左边的话就说明n小于这个常数于是者就变成了常数级别的算法。

但是搞不清楚这样这么处理，不过CCF也应该注意到了这个问题，于是数据没有太毒瘤，比如以下这种

1

4 O(n^1)

F i n 3

F j 4 n

E

E

按道理答案既可以是O（1）也可以是O（n^1）,很奇怪的是，我的代码如果是O（1）也能输出Yes，O（n^1）也能输出Yes，第一篇题解是O（1）才能输出yes

这个东西太玄学了，这个O(1),O(N)也是要看N的

2.循环变量名怎么判断重复。

目前看起来循环变量名只有一位，本人在做题的时候感觉有可能出现好几位的变量名（毕竟长度不超过100），于是写了个哈希。

其实只需要加一个标记数组标记一下就好了。

3.循环结束后怎样取消被标记的变量

开一个栈，随着循环F加到栈顶E弹出栈的时候同时取消标记即可。

其实这块地方我用了两个栈，第一个（st）存变量名，第二个（looker）存这个变量是否对这个循环复杂度有影响（有的话是1，没有的话是0）

4.那么一个循环F a x y 当x>y的时候以下循环怎么办

创建一个变量（我这段代码是niup），当出现这种情况的时候niup++

再开一个栈，出现这种情况的时候向栈内压一个1，不是这种情况的时候压一个0，每次E弹栈的时候，如果栈顶是1,niup–

最大循环的复杂度只有在niup==0的时候才能比较。

至于为什么是++而不是直接设为1，是因为这样的情况在一个F循环里面可能嵌套了好几个。所以不能这样搞。

5.你的代码怎么过不去？

我也不知道啊，我开了O2就（WA->AC）了

6.你的代码怎么还过不去？

我对代码做了点手脚，你应该看得出来，而且我希望你们重温一下我的惨痛经历。（你直接跳到最下面就应该知道我怎么了）

那么我们来看代码吧

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
#include<touwenjian.h>

using namespace std;

int n;
string s,fors;

inline int getdight(int nowi)
{
	int x=0;
	for(register int i=nowi;i<s.size();i++)
	{
		if(s[i]>'9'||s[i]<'0') return x;
		x=x*10+s[i]-'0';
	}
	return x;
}

inline int getdig(string s1)
{
	int x=0;
	for(register int i=0;i<s1.size();i++)
	{
		x=x*10+s1[i]-'0';
	}
	return x;
}

inline int getlen()
{
	register int i,j;
	j=s.size();
	for(i=0;i<j;i++)
	if(s[i]=='(')
	{
		if(s[i+1]=='1') return 0; //只有O（1） 才会是'('右边为1
		if(s[i+1]=='n') 
		{
			i+=3;  //直接跳到数字部分
			return getdight(i);
		}
	}
}

inline int gethash(string t)
{
	unsigned int x=0;
	for(register int i=0;i<t.size();i++) x=x*19260817+int(t[i]-'a');
	return x%457+1;
}

inline void slove(int m,int mutif)
{
	stack <int> st;
	stack <int> looker;
	stack <int> looker2;
	register int i,j;
	int bj[500];  //上面讲的很清楚，记得每次清空bj数组
	memset(bj,0,sizeof(bj));
	string f,l,r,x;
	int ce=0,realf=0,mmxf=0;
	int numf=0,nume=0;
	int niup=0;
	for(i=1;i<=m;i++)
	{
		cin>>f;
		if(f=="F") numf++,cin>>x>>l>>r;
		if(ce) continue;
		if(f=="E") 
		{
			if(nume+1>numf) 
			{
				ce=1;
				continue;
			}
			bj[st.top()]=0;
			st.pop();
			if(looker.top()) realf--;
			looker.pop();
			if(looker2.top()) niup--;
			looker2.pop();
			nume++;  //这里就是对应的处理方法nume是E的S
			continue;
		}
		int hx=gethash(x);
		if(bj[hx]) ce=1,st.push(hx);
		else 
		{
			bj[hx]=1;
			int nl,nr;
			if(l!="n") nl=getdig(l);
			if(r!="n") nr=getdig(r); 
			if(r=="n"&&l!="n") looker2.push(0),looker.push(1),st.push(hx),realf++;
			else 
			{
				st.push(hx),looker.push(0);
				if(nr<nl) niup++,looker2.push(1);
				else looker2.push(0);
			}
			if(!niup) mmxf=max(realf,mmxf);
		}
	}
	if(ce||numf!=nume) cout<<"Err"<<endl;  //E 与 F 必须要数量相等
	else if(mmxf==mutif) cout<<"Yes"<<endl;
	else if(mmxf!=mutif) cout<<"No"<<endl;
	return ;

}

int main()
{
	ios::sync_with_stdio(false); 
	register int i,j,t;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>t;
		cin>>s;
		int mutilen=getlen();
		slove(t,mutilen);
	}
	return 0;
}

答案揭秘

ERR要大写