2018.11.02 洛谷P3952 时间复杂度(模拟)
程序员文章站
2022-03-14 19:48:38
...
传送门
惊叹考场。
这题还没有梭哈难啊233.
直接按照题意模拟就行了。
代码:
#include<bits/stdc++.h>
using namespace std;
int T,n,typ,dep[105];
bool f;
inline int calc(char s[]){
int len=strlen(s);
int ret=0,pos=0;
for(;pos!=len;++pos)if(isdigit(s[pos]))break;
while(isdigit(s[pos])&&pos!=len)ret=(ret<<3)+(ret<<1)+(s[pos]^48),++pos;
return ret;
}
int main(){
freopen("lx.in","r",stdin);
scanf("%d",&T);
while(T--){
stack<char>S;
set<char>exi;
char s[10];
int tot=0,now=0,ans=0;
memset(dep,0,sizeof(dep));
while(!S.empty())S.pop();
exi.clear(),scanf("%d%s",&n,&s),typ=0,f=1;
if(s[2]!='1'){
int len=strlen(s);
for(int i=4;i<len;++i){
if(!isdigit(s[i]))break;
typ=(typ<<3)+(typ<<1)+(s[i]^48);
}
}
int i=1;
for(;i<=n;++i,ans=max(ans,dep[now])){
scanf("%s",s);
if(s[0]=='E'){
if(!S.size()){f=0;break;}
exi.erase(S.top()),S.pop(),--now;
}
else{
scanf("%s",s);
char x[5],y[5];
scanf("%s%s",x,y);
if(exi.count(s[0])){f=0;break;}
S.push(s[0]),exi.insert(s[0]),++now;
if(dep[now-1]==-1){dep[now]=-1;continue;}
if(x[0]=='n'){
if(y[0]=='n'){dep[now]=dep[now-1];continue;};
dep[now]=-1;continue;
}
if(y[0]=='n'){dep[now]=dep[now-1]+1;continue;}
int X=calc(x),Y=calc(y);
if(X<=Y){dep[now]=dep[now-1];continue;}
else dep[now]=-1;
}
}
++i;
for(;i<=n;++i){
scanf("%s",s);
if(s[0]=='F')scanf("%s",s),scanf("%s",s),scanf("%s",s);
}
if(S.size())f=0;
if(f){
if(typ^ans)puts("No");
else puts("Yes");
}
else puts("ERR");
}
return 0;
}