Luogu P3952 时间复杂度

作为一道模拟题，码量适中，细节妥当，数据用心，好评。

就是有些细节你不看数据真的想不到，当然也有可能是我太菜了

离线做，个人认为比较便于调试。

转离线代码：

struct node {
	bool type; //true-F false-E
	char var;
	int l,r; //INF-n
};

node Tran(char *s) {
	int pos;
	node ret=(node){false,0,0,0};
	if(s[0]=='E') {
		return ret;
	}
	ret.type=true;
	ret.var=s[2];
	if(s[4]=='n') {
		ret.l=INF;
		if(s[6]=='n') {
			ret.r=INF;
		}
		else {
			ret.r+=s[6]-'0';
			pos=7;
			while(s[pos]!='
') {
				ret.r*=10,ret.r+=s[pos]-'0';
				pos++;
			}
		}
	}
	else {
		ret.l+=s[4]-'0';
		pos=5;
		while(s[pos]!=' ') {
			ret.l*=10,ret.l+=s[pos]-'0';
			pos++;
		}
		pos++;
		if(s[pos]=='n') {
			ret.r=INF;
		}
		else {
			ret.r+=s[pos]-'0';
			pos++;
			while(s[pos]!='
') {
				ret.r*=10,ret.r+=s[pos]-'0';
				pos++;
			}
		}
	}
	return ret;
}

个人认为比较核心的是这个 $ ext{FindMatch}$ 函数：其实就是实现了一个类似常用编程语言中括号匹配的功能。

int FindMatch(int x) {
	if(nod[x].type) {
		int ret=x+1,cnt=1;
		while(ret!=L+1) {
			if(nod[ret].type) {
				cnt++;
			}
			else {
				cnt--;
			}
			if(cnt==0) {
				return ret;
			}
			ret++;
		}
	}
	else {
		int ret=x-1,cnt=-1;
		while(ret!=0) {
			if(nod[ret].type) {
				cnt++;
			}
			else {
				cnt--;
			}
			if(cnt==0) {
				return ret;
			}
			ret--;
		}
	}
	return -1;
}

需要注意的几个点：

• 在遇到 $ exttt{E}$ 的一行时，要先看一下它对应的那行 $ exttt{F}$ 有没有贡献复杂度，再考虑这里要不要将复杂度减小。

• 读入的时候分清四种情况。

• 读到 $ exttt{n}$ 的处理：这里我将其赋值为 $ exttt{INF} (2^{32}-1)$，便于之后直接用数值判断。

完整代码如下：

#include<bits/stdc++.h>
#define N 110
#define INF 0x7FFFFFFF
#define debug printf("OK
");

int t,L,giv,cal,maxcal,ans; //ans:1-Yes 2-No -1-ERR
int match[N];
bool vis[30],ctb[N];

struct node {
	bool type; //true-F false-E
	char var;
	int l,r; //INF-n
};

node nod[N];

namespace WalkerV {
	void Init() {
		giv=0,cal=0,maxcal=0,ans=0;
		memset(vis,false,sizeof(vis));
		memset(ctb,false,sizeof(ctb));
		memset(nod,0,sizeof(nod));
		return;
	}

	node Tran(char *s) {
		int pos;
		node ret=(node){false,0,0,0};
		if(s[0]=='E') {
			return ret;
		}
		ret.type=true;
		ret.var=s[2];
		if(s[4]=='n') {
			ret.l=INF;
			if(s[6]=='n') {
				ret.r=INF;
			}
			else {
				ret.r+=s[6]-'0';
				pos=7;
				while(s[pos]!='
') {
					ret.r*=10,ret.r+=s[pos]-'0';
					pos++;
				}
			}
		}
		else {
			ret.l+=s[4]-'0';
			pos=5;
			while(s[pos]!=' ') {
				ret.l*=10,ret.l+=s[pos]-'0';
				pos++;
			}
			pos++;
			if(s[pos]=='n') {
				ret.r=INF;
			}
			else {
				ret.r+=s[pos]-'0';
				pos++;
				while(s[pos]!='
') {
					ret.r*=10,ret.r+=s[pos]-'0';
					pos++;
				}
			}
		}
		return ret;
	}

	void Read() {
		int pos;
		char s[20];
		scanf("%d%s",&L,s);
		if(s[2]=='1') {
			giv=0;
		}
		else {
			giv+=s[4]-'0';
			pos=5;
			while(s[pos]!=')') {
				giv*=10,giv+=s[pos]-'0';
				pos++;
			}
		}
		getchar();
		//printf("giv:%d
",giv);
		for(int i=1;i<=L;i++) {
			memset(s,0,sizeof(s));
			pos=-1;
			while(s[pos]!='
') {
				s[++pos]=getchar();
			}
			//printf("%s",s);
			nod[i]=Tran(s);
			//printf("type:%d var:%c l:%d r:%d
",nod[i].type,nod[i].var,nod[i].l,nod[i].r);
		}
		return;
	}

	int FindMatch(int x) {
		if(nod[x].type) {
			int ret=x+1,cnt=1;
			while(ret!=L+1) {
				if(nod[ret].type) {
					cnt++;
				}
				else {
					cnt--;
				}
				if(cnt==0) {
					return ret;
				}
				ret++;
			}
		}
		else {
			int ret=x-1,cnt=-1;
			while(ret!=0) {
				if(nod[ret].type) {
					cnt++;
				}
				else {
					cnt--;
				}
				if(cnt==0) {
					return ret;
				}
				ret--;
			}
		}
		return -1;
	}

	void Solve() {
		for(int i=1;i<=L;i++) {
			match[i]=FindMatch(i);
			if(match[i]==-1) {
				ans=-1;
				return;
			}
			//printf("match:%d
",FindMatch(i));
			if(nod[i].type) {
				if(vis[nod[i].var-'a'+1]) {
					ans=-1;
					return;
				}
				vis[nod[i].var-'a'+1]=true;
			}
			else {
				vis[nod[match[i]].var-'a'+1]=false;
			}
			if(nod[i].l!=INF&&nod[i].r==INF) {
				ctb[i]=true;
			}
		}
		for(int i=1;i<=L;i++) {
			if(!nod[i].type) {
				//printf("col:%d cal:%d maxcal:%d
",i+2,cal,maxcal);
				maxcal=std::max(maxcal,cal);
				if(ctb[match[i]]) {
					cal--;
				}
				continue;
			}
			if(nod[i].l>nod[i].r) {
				//printf("jump:%d->%d l:%d r:%d
",i+2,match[i]+2,nod[i].l,nod[i].r);
				i=match[i];
				continue;
			}
			if(nod[i].l!=INF&&nod[i].r==INF) {
				cal++;
			}
		}
		if(giv==maxcal) {
			ans=1;
		}
		else {
			ans=2;
		}
		return;
	}

	void Print() {
		//printf("cal:%d
",maxcal);
		switch(ans) {
			case 1:
				printf("Yes
");
				break;
			case 2:
				printf("No
");
				break;
			case -1:
				printf("ERR
");
				break;

		}
		return;
	}
}

int main() {
	scanf("%d",&t);
	for(int i=1;i<=t;i++) {
		WalkerV::Init();
		WalkerV::Read();
		WalkerV::Solve();
		WalkerV::Print();
	}
	return 0;
}