时间复杂度

题目大意

这个自己看吧，noip2017的D1T2

solution

先介绍一下这道题我们用到的每个变量他们的用处

stack[]记录变量的循环层
vis[]记录变量在栈中是否出现过
cmp函数，这个可以用作比较循环中a和b的大小

\[\begin{cases}
a<b -> 进入新的一层循环\\
a>b -> 无法进入新的循环，循环终止\\
a=b -> 此循环为o1
\\
\end{cases}
\]

stop 如果循环已经无法进入，那么就用stop计数
ans表示最终的复杂度层数，maxn表示当前一层循环的复杂度层数

接下来是三种状态的
ERR 条件

\[\begin{cases}
F、E不匹配\\
变量名重复
\\
\end{cases}
\]

No，Yes均为题目定义

呼。然后就是代码了

首先你得会字符串处理一系列问题，如w，a，b之类的数字值，然后你得会普通的栈思想。

接下来第一步，我们如何处理复杂度问题。我的思路是分o1和on方的

o1你得判断他的循环层数不得为正整数，然后判一下ERR就可以了。

on方的话，你要准确判断他的循环层数

然后就是cmp函数，我的整段代码的精妙就全在cmp函数里了。

cmp函数判断的是a和b的值。

首先如果b不是n，那么他就不会形成一个循环层

其次如果数为n，那么就赋为inf

然后如果两个数如果都是数字，那么就为o1，直接按照相等处理

AC代码！

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;

const int inf = 2147483647;

char s[200],a[200],b[200];

char stack[200];

char F,id;

int top;

bool vis[200],ERR;

int cmp(char *a,char *b) {

	int an=0,bn=0;

	if(a[0]=='n') an=inf;

	else {

		for(int i=0; i<strlen(a); i++)

			an=an*10+a[i]-'0';

	}

	if(b[0]=='n') bn=inf;

	else {

		for(int i=0; i<strlen(b); i++)

			bn=bn*10+b[i]-'0';

	}

	if(an>bn) return -1;

	if(an<bn && bn==inf) return 1;

	if(an==bn) return 0;

}

int main() {

	int T;

	scanf("%d",&T);

	while(T--) {

		int n;

		memset(s,0,sizeof(s));

		memset(vis,0,sizeof(vis));

		memset(stack,0,sizeof(stack));

		top=0;

		scanf("%d",&n);

		cin >> s;

		int maxn=0,ans=0;

		int stop=0;

		ERR=false;

		memset(a,0,sizeof(a));

		memset(b,0,sizeof(b));

		if(s[2]=='1') {

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

				cin >> F;

				if(F=='E') {

					if(stop)stop--;

					vis[stack[top--]]=false;

					if(top==0) {

						ans=max(ans,maxn);

						maxn=0;

					}

					if(top<0)ERR=true;

				} else if(F=='F') {

					cin >> id;

					if(vis[id]) ERR=true;

					else vis[id]=1;

					stack[++top]=id;

					memset(a,0,sizeof(a));

					memset(b,0,sizeof(b));

					cin >> a >> b;

					if(stop) {

						stop++;

						continue;

					}

					int flag=cmp(a,b);

					if(flag==1) if(top>maxn)maxn++;

					if(flag==-1) stop++;

				}

			}

			if(top || ERR) {

				printf("ERR\n");

				continue;

			}

			if(ans!=0) {

				printf("No\n");

				continue;

			}

			printf("Yes\n");

		}

		if(s[2]=='n') {

			int num=0;

			for(int i=0; i<strlen(s); i++)

				if(s[i]>='0'&&s[i]<='9')num=num*10+s[i]-'0';

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

				cin >> F;

				if(F=='E') {

					if(stop)stop--;

					vis[stack[top--]]=false;

					if(top==0) {

						ans=max(ans,maxn);

						maxn=0;

					}

					if(top<0)ERR=true;

				} else if(F=='F') {

					cin >> id;

					if(vis[id]) ERR=true;

					else vis[id]=1;

					stack[++top]=id;

					memset(a,0,sizeof(a));

					memset(b,0,sizeof(b));

					cin >> a >> b;

					if(stop) {

						stop++;

						continue;

					}

					int flag=cmp(a,b);

					if(flag==1) if(top>=maxn+1)maxn++;

					if(flag==-1) stop++;

				}

			}

			if(top || ERR) {

				printf("ERR\n");

				continue;

			}

			if(ans!=num) {

				printf("No\n");

				continue;

			}

			printf("Yes\n");

		}

	}

	return 0;

}

tips:还有一件事请非常的重要，做模拟题之前，一定要理清思路，最好写在纸上，因为码量大的题目很容易会健忘，这样会有以思维时间换代码时间，垃圾思维大幅度缩短。

你会发现我曾经wa了无数发，都是没有认真思考的结果！

复杂度

luogu 3952 时间复杂度（模拟）

时间复杂度

题目大意

solution