洛谷 P3952 时间复杂度【模拟】

把No写成NO，WA了一发……

现在看这题也不难……

用一个栈，记一下前面F的字母，是否合法，合法的有多长，每次入栈弹栈即可

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=105;

int T,n,top,co[305],mx,fl,er,va;

char o[10],c[N];

struct qwe

{

	char c;

	int fl,va;

}s[N];

int main()

{

	scanf("%d",&T);

	while(T--)

	{

		scanf("%d%s\n",&n,o);//cerr<<"    "<<n<<endl;

		top=0,mx=0,fl=0,er=0,va=0;

		memset(co,0,sizeof(co));

		for(int i=1;i<=n;i++)

		{

			gets(c);//cerr<<"???"<<i<<" "<<c<<endl;

			if(c[0]=='E')

			{

				if(!top)

					er=1;

				else

				{

					co[s[top].c]--;

					fl-=s[top].fl;

					va-=s[top].va;

					top--;

				}

			}

			else

			{

				if(co[c[2]])

					er=1;

				s[++top].c=c[2];

				co[c[2]]++;

				int w=4,x=0,fx=-1,y=0,fy=-1;

				while(c[w]>='0'&&c[w]<='9')

					fx=1,x=x*10+c[w]-48,w++;

				w=max(w+1,6);

				while(c[w]>='0'&&c[w]<='9')

					fy=1,y=y*10+c[w]-48,w++;

				// cerr<<fx<<" "<<x<<"   "<<fy<<" "<<y<<endl;

				if((fx==-1&&fy!=-1)||(fx!=-1&&fy!=-1&&x>y))

					s[top].fl=1,fl++;

				else

					s[top].fl=0;

				if(fx!=-1&&fy==-1)

					s[top].va=1,va++;

				else

					s[top].va=0;

				if(!fl)

					mx=max(mx,va);

			}

		}

		if(top)

			er=1;

		int x=0,w=4;

		while(o[w]>='0'&&o[w]<='9')

			x=x*10+o[w]-48,w++;

		// cerr<<x<<" "<<mx<<endl;

		if(er)

			puts("ERR");

		else if((o[2]=='n'&&mx==0)||(o[2]=='n'&&mx!=x))

			puts("No");

		else

			puts("Yes");

	}

	return 0;

}