在 $2024$ 年的一场由我们教练在赛前举办的只有两题的不知道叫什么的比赛中，我在赛时通过了这题，并取得了 AK 的成绩，因此写一篇题解。

Solution P3952

题意疏通

对于模拟题我们一般先把题意捋清楚。

我们的任务是把小明的程序的时间复杂度算出来，同时判断里面有没有语法错误。

我们先从简单入手。

ERR 的判断

如何判断 ERR？ERR 有两个方面：F 和 E 不匹配或新建的变量与已经存在但未被销毁的变量重复。

对于第一种情况，我们只需要拿一个栈，到最后判断是否为空就可以了。

对于第二种情况，我们可以拿一个 map 记录已经存在的循环变量的个数，如果个数大于 $1$，就会 ERR。

时间复杂度的计算

这一部分是一个难题。

对于时间复杂度的计算，一个循环中 F i x y 的 $x$ 和 $y$ 无非只有 $4$ 种情况：

• $x$ 为 $n$，$y$ 为常数。这种情况是不会执行的。
• $x$ 为常数，$y$ 为 $n$。这种情况下，该循环需要执行 $n$ 次（事实上是接近于 $n$ 次看做 $n$），对总复杂度的加成为乘 $Θ(n)$。
• $x$ 和 $y$ 均为常数且 $x<y$。这种情况下对总复杂度的加成是乘 $Θ(1)$。或者说不变。
• $x$ 和 $y$ 均为常数且 $x>y$。这种情况是不会执行的。

注意到如果一个循环外层有不会执行的循环，那么这个循环也不会执行。就像下面的代码一样：

for(int i=1;i<=0;i++){
    for(int j=1;j<=n;j++){
      for(int k=1;k<=3;k++)//Code
  }
}

可以看到虽然第二层、第三层循环单独拿出来都可执行，但是第一层循环无法执行，所以后面两层嵌套在里面就无法执行了。

我们对于循环的记录，用栈来记录（很显然循环这种东西也非常符合栈先进先出的特点）。至于具体的写法，我们还是看下面的代码吧。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
map<string, int> mp;
// mp 用来记录每个循环变量的出现次数
stack<int> st;
// st 用于把循环压入栈
stack<string> st2;
// st2 记录循环变量名
string ss, a, b, c, d;
// 输入的字符串
int l, T, want, s, t, ans, cnt, tot;
/*
l:循环层数
T:多测数据组数
want:小明计算出的时间复杂度要我们验证的
s:循环开始的数
t:循环结束的数
ans:我们自己算出的时间复杂度
cnt:s>t 型循环的数目
tot:一次循环复杂度为 O(n) 的循环的数目
*/
int main()
{
    scanf("%d", &T); // 多测
    while (T--)
    {
        scanf("%d", &l); // 读入循环个数
        cin >> ss;
        want = 0;
        mp.clear();
        while (!st.empty())
            st.pop();
        ans = 0;
        if (ss == "O(1)")
            want = 0;
        else
        {
            for (int i = 0; i < ss.length(); i++)
            {
                if ('0' <= ss[i] && ss[i] <= '9')
                    want = want * 10 + ss[i] - '0';
            }
        }
        bool f = 0, ff = 1;
        tot = 0;
        cnt = 0;
        while (l--)
        {
            cin >> a;
            if (a == "E")
            {
                if (st.empty())
                { // 结束比开始多
                    f = 2;
                }
                else
                {
                    if (st.top() == -1)
                        cnt--; // 如果是无法执行的循环结束
                    else if (st.top() == 1 && !cnt)
                        tot--; // 如果可执行的循环结束
                    st.pop();
                    mp[st2.top()]--; // 剔除循环变量
                    st2.pop();
                }
            }
            else
            {
                cin >> b >> c >> d;
                if (mp[b])
                    f = 1; // 如果循环变量重复
                s = 0;     // 记录循环起值
                t = 0;     // 记录循环终值
                mp[b]++;
                if (c == "n")
                    s = 114514; // 如果是 n 开始那就把 s 设为极大值
                else
                {
                    for (int i = 0; i < c.length(); i++)
                    {
                        s = s * 10 + c[i] - '0';
                    } // 否则提取 s
                }
                if (d == "n")
                    t = 114514; // t 同理
                else
                {
                    for (int i = 0; i < d.length(); i++)
                    {
                        t = t * 10 + d[i] - '0';
                    }
                }
                st2.push(b);
                if (t - s >= 100000)
                { // t 若为 114514-smax(100)=114414，这里为了保险
                    if (!cnt)
                        tot++;           // 增加一层循环
                    ans = max(ans, tot); // 求出最大时间复杂度
                    st.push(1);          // 塞进去一层可执行循环
                }
                else if (t < s)
                {
                    cnt++;
                    st.push(-1); // 不可执行循环，妨碍后面执行
                }
                else
                    st.push(0); // 其他情况，不必处理
            }
            if (!st.empty() || f)
                printf("ERR\n"); // 如果循环变量重复或者开始和结束不匹配
            else if (want == ans)
                printf("Yes\n"); // 时间复杂度正确
            else
                printf("No\n"); // 错误
        }
        return 0;
    }
}