欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.11.02 洛谷P3952 时间复杂度(模拟)

程序员文章站 2022-03-14 19:48:38
...

传送门
惊叹考场dubuffdubuff
这题还没有梭哈难啊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;
}
相关标签: 模拟