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

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

需要注意的几个问题:

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要大写