题解 P3952 【时间复杂度 】
whyl
2019-06-30 11:03:29
这道题很显然是一道模拟
在我历经2个小时的调试中
终于写完了这篇AC代码
讲下具体做法吧
就是用一个栈来维护你的字符和你要算出来的时间复杂度
判断一些可能出现的情况
再打标记并且处理掉就OK啦！
模拟是一个noip常考考点
希望大家能多练习
谢谢观看！
```
#include<bits/stdc++.h>
using namespace std;
int t,n,flag,top,duan,tong[1004],fz[105],biaoji,ans,tot,shangdibiaoji;
char s[3000005];
inline void bian(int &flag,string a){
if(isdigit(a[4])&&isdigit(a[5])) flag=(a[4]-'0')*10+(a[5]-'0');
else flag=a[4]-'0';
}
inline void init(string a){
if(a[2]=='n'){
bian(flag,a);
}
else flag=0;
}
void zhuanhua(int &aa,string a){
int len=a.length();
if(len==1){
aa=(a[0]-'0');
return;
}
if(len==2){
aa=(a[0]-'0')*10+(a[1]-'0');
return;
}
}
inline void check(){
top=0;tot=0;ans=0;duan=0;shangdibiaoji=0;
while(n--){
char opt;
cin>>opt;
if(opt=='F'){
char buf;
cin>>buf;
if(tong[buf]){
shangdibiaoji=1;
top+=10000;
}
tong[buf]=1;
s[++top]=buf;
string a,b;
int aa,bb;
cin>>a>>b;
if(duan){
fz[top]=fz[top-1];
continue;
}
if(a=="n"&&b=="n"){
fz[top]=fz[top-1];
continue;
}
if(a=="n"){
fz[top]=fz[top-1];
duan=1;
biaoji=top-1;
continue;
}
if(b=="n"){
fz[top]=fz[top-1]+1;
continue;
}
if(a!="n"&&b!="n"){
zhuanhua(aa,a);zhuanhua(bb,b);
if(aa>bb){
duan=1;
biaoji=top-1;
continue;
}
fz[top]=fz[top-1];
continue;
}
}
else{
if(top==0){
shangdibiaoji=1;
top+=10000;
}
ans=max(ans,fz[top]);
if(!duan) fz[top]=0;
tong[s[top--]]=0;
if(biaoji==top) duan=0;
}
}
if(shangdibiaoji){
cout<<"ERR\n";
return;
}
if(top){
cout<<"ERR\n";
return;
}
if(ans==flag){
cout<<"Yes\n";
return;
}
else cout<<"No\n";
}
int main(){
ios::sync_with_stdio(0);
cin>>t;
while(t--){
memset(tong,0,sizeof(tong));
cin>>n;string a;
cin>>a;
init(a);
check();
}
return 0;
}
```