题解 | #时间复杂度#

误点一：输入是使用的是字符串形式，误当做整数来运算，例如'10'，直接和'1'比较大小，复杂度同样，输入的时候也是字符串形式，需要转换成数字形式

误点二：可能有F i n n 的情况，这时n位于b的位置，不属于循环终止的情况

误点三：1.只判断了可能E在F之前，例如F E E F，F可能在最后，导致循环不终止。2.E和F次数不匹配，可能E比F多，例如F F E E E,这种情况也属于ERR

误点四：要考虑循环逐层退出的情况，退出每一层都要逐层记录，同时记录a位置的小写字母的使用情况

思路就是直接模拟，判断特殊情况，记录循环层数和字母使用情况

#include<bits/stdc++.h>

using namespace std;

char e[110];

int main()
{
	int t;
	cin >> t;
	while(t -- )
	{
		int l;
        string s;
		cin >> l >> s;
		
		map<char , int > d;
		int res = 0, y = 0, o = 0, m = 0, ans = 0, O = 0,mal = 0, r = 0, v = 0;
		for(int i = 1; i <= l; i ++ )
		{
			char x;
			cin >> x; 
			if(x == 'F')
			{
                r++;//记录F出现次数
				res ++;//记录F的循环层数
				char a;
                string b, c;
				cin >> a >> b >> c;
				if(d[a] == 1)//判断a是否再次出现导致ERR
				{
					y = 1;
				}
				if(d[a] == 0) d[a] = 1,e[mal++] = a;//记录字母出现，同时存入出现的字母
				if(b[0] == 'n' && m == 0 && c[0] != 'n') {m ++;}//记录无法进入循环的F
                if(b[0] != 'n' && c[0] != 'n')//两个数字比较大小
                {
                    int p1 = b.size();
                    int p2 = c.size();
                    int p3,p4;
                    if(p1 == 1)  p3 = (b[0] - '0');
                    else if(p1 == 2) p3 = (b[0] - '0')*10 + (b[1] - '0');
                    //字符串转换为数字
                    if(p2 == 1) p4 = (c[0] - '0');
                    else if(p2 == 2) p4 = (c[0] - '0')*10 + (c[1] - '0');
                    //字符串转换为数字
                    if(p4 < p3) {m ++;}//无法进入循环
                }
				if(c[0] == 'n' && m == 0 && b[0] != 'n'){
                    o ++;
                }
			}
			if(x == 'E')
            {
                mal--;
                d[e[mal]] = 0;//清空字母出现次数
                e[mal] = 0;//清除当前字母
                if(res > 0) {res --;}
                O = max(O, o);//最大时间复杂度
                if(o > 0 && m == 0) {o -- ;}
                if(m > 0) {m --;}
                v++;//记录E出现次数
                
            }
		}
		if(res > 0 || r != v)
		{
			cout << "ERR" << endl;
			continue;
		}//E和F不匹配
		if(y == 1)
		{
			cout << "ERR" << endl;
			continue;
		}//新建的变量与已经存在但未被销毁的变量重复
		if(O == 0)
		{
			if(s[2] != '1') cout << "No" << endl;
			else cout << "Yes" << endl;
		}
		else
		{
			if(s[2] == 'n' && s[3] == '^')
			{
				int p5 = s.size()-5;
                int p6;
                if(p5 == 1) p6 = (s[4] - '0');
                else if(p5 == 2) p6 = (s[4] - '0')*10 + (s[5] - '0');
                //时间复杂度转换成数字
                if(p6 == O) cout << "Yes" << endl;
				else cout << "No" << endl;
			}
			else cout << "No" << endl;
		}
	}
	return 0;
}