题解

题目分析

这是一道基于栈和字符串处理的题目，需要解析程序结构并计算复杂度。

解题思路

1. 问题建模

• 解析程序结构，识别循环语句
• 计算程序的时间复杂度
• 使用栈维护程序结构

2. 栈结构

• 使用 stack<string> 维护程序结构
• 处理嵌套的循环语句
• 支持 F 和 E 语句的匹配

3. 循环处理

• 识别 F 语句：开始循环
• 识别 E 语句：结束循环
• 处理循环变量的范围

4. 复杂度计算

• 分析循环的嵌套层次
• 计算时间复杂度
• 处理特殊情况

5. 关键技巧

• 使用栈维护程序结构
• 处理变量名冲突
• 计算循环次数

6. 算法实现

• 栈操作：$O(n)$
• 复杂度计算：$O(n)$
• 总体复杂度：$O(n)$

时间复杂度

$O(n)$，其中 $n$ 为程序语句数。

#include<bits/stdc++.h>
using namespace std;
int t,n,icf,xy[105];
string x,y,name,namei[105],s,e;
stack<string> stk;
int main(){
	cin>>t;
	while(t--){
		cin>>n>>s;
		for(int i=0;i<=n;i++) xy[i]=0;
		while(!stk.empty()) stk.pop();
		int f=0,mt=0,st=0,fe=0,sstk=0;
		for(int i=1;i<=n;i++){
			cin>>e;
			if(e=="F"){
				cin>>name>>x>>y;
				namei[++sstk]=name;
				stk.push(e);
				if(!f){
					if(x=="n"&&y!="n")
						f=1,xy[sstk]=1;
					if(x!="n"&&y!="n"){
						if(x.size()>y.size()) f=1,xy[sstk]=1;
						else{
							int xx,yy;
							if(x.size()==y.size())
								if(x>y) f=1,xy[sstk]=1;
						}
					}
					if(x!="n"&&y=="n") st++;
				}
			}
			else{
				namei[sstk]="";
				mt=max(mt,st);
				if(!f&&st) st--;
				if(xy[sstk]) f=xy[sstk]=0;
				if(!stk.empty()) stk.pop();
				else fe=1;
				sstk--;
			}
			for(int i=1;i<=sstk;i++)
				for(int j=1;j<=sstk;j++)
					if(namei[i]==namei[j]&&i!=j)
						fe=1;
		}
		if(fe||!stk.empty()){
			cout<<"ERR\n";
			continue;
		}
		if(s.size()==4) icf=0;
		if(s.size()==6) icf=s[4]-'0';
		if(s.size()==7) icf=(s[4]-'0')*10+s[5]-'0';
		if(mt==icf) cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
/*
1
12 O(n^4)
F a 50 n
F b 6 78
F c 9 10
F d 6 n
F e 17 n
F f 24 n
E
E
E
E
E
E
*/