题解 | #时间复杂度#

模拟题，考察耐心和细节。

做了将近三个小时，连改带调的写了出来。遇到了不少坑点，也熟悉了一些淡忘的知识点。

①：gets现在一般不用了，用的是fgets(s,sizeof(s),stdin)。直接用gets会报错。

②：gets本身读入是遇到'\n'就结束，但本身也把'\n'读进去了，所以在循环中不需要重复getchar()，不然会错误。

③：在读gets()之前要清空前面的'\n'，不然会默认读了'\n'。（此题显然前面只有一个'\n'）

一些细节上的坑点：

①：关于F中存在的非法情况的处理，（非法即x>y）当存在某一个F非法了，那么当该F遇见他的E之前，下面的循环F都没有意义。

②：类似FFFE的情况，当顶层的F遇见了他的E之后，那么这个F中的变量i又可以重新被后面的F使用了。

③：类似FFFE的情况，如果顶层的F是非法的，那么当他遇见了他的E之后，他就不会再影响后面的F。也就是说下面的F又重新有了意义。

同时这道题的数据比较水。牛客和洛谷上数据点不同，开始没考虑到上述②中的问题，牛客上居然A了，但洛克卡了一个点。同时，我开始没写函数fu[107]，直接每一次读到E都强行让ans--，这居然也A了。而且牛客和洛谷都能过，只能说数据有待加强。

其他的一些问题具体在代码上体现，同时有注释。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<stack>
using namespace std;
bool b[30];// 记录某个小写字母在当时的for循环内部是否重复出现
int he[107] = { 0 };//用作判断当前的F是否非法
int fu[107] = { 0 };//记录复杂度为O(n)的F
string ss;
int turn()
{
    int tmp = 0;
    for (int i = 4; i < ss.length(); i++)
    {
        if (ss[i] < '0' || ss[i]>'9')break;
        tmp = tmp * 10 + ss[i] - '0';
    }
    return tmp;
}
int main()
{
    int t; cin >> t;
    char s[20];
    int len;
    while (t--)
    {
        scanf("%d", &len);
        cin >> ss;
        memset(he, 0, sizeof he);
        memset(fu, 0, sizeof fu);
        int tmp = 0, flag = 0, ans = 0,maxx = 0;
        stack<int>st;//存F，遇E去掉最上面的F。在这里存每一个F中的变量，等价。
        stack<int>sta;//存非法for循环中的节点，以及该for循环中的变量
        if (ss[2] == 'n')tmp = turn();
        else if (ss[2] == '1')tmp = 0;//O(1)时，设定答案为0。其他O(n^m)设定答案为m。
        getchar();//吸收换行符
        for (int now = 1; now <= len; now++)
        {
            fgets(s, sizeof(s), stdin);//等价gets
            int cnt = 1;//记录F时候是i x y的哪一个
            int a[5] = { 0 };
            int m = 1, zi = 0;
            if (st.empty())//st为空，说明这时是一个新的for循环了，之前的没有了。
            {
                maxx = max(ans, maxx);//更新一下答案
                ans = 0;// 清0
                memset(b, 0, sizeof b);//对于新的for循环，存字母是否出现的b也要清零
                memset(he,0,sizeof he);//he数组同样要清零
                memset(fu,0,sizeof fu);//同上
            }
            for (int i = 0; i < strlen(s); i++)
            {
                if (flag == -1)break;//flag为-1说明是ERR，只需要等待输入完就行了。
                if (s[i] == ' ')continue;
                if (s[i] == 'E')
                {
                    if (st.empty()) { flag = -1; break; }//非法情况，E和F对不上
                    maxx = max(ans, maxx);//更新答案
                    int q = st.top();
                    if (fu[q])ans--;//因为读入了一个E，说明循环减少了一层，而且只有当这个F是O(n)，才需要ans--，其他不需要改变。
                    b[st.top()] = 0;//读入了E，就把当前F中的变量改值，表示这个变量又可以出现了。
                    if (he[q] == 1)//当he[p]=1，说明最上层的F是非法的F。也就是i x y里，x>y的情况，即无法进入循环。
                    {
                        sta.pop();//清除了一个非法的F
                    }
                    st.pop();
                    continue;
                }
                if (s[i] == 'F')
                {
                    cnt = 1;
                    continue;
                }
                if ('a' <= s[i] && s[i] <= 'z')
                {
                    if (cnt == 1)
                    {
                        int c = s[i] - 'a' + 1;
                        if (b[c] == 1) { flag = -1; }
                        st.push(c);
                        b[c] = 1;
                        zi = c;
                        cnt++;
                    }
                    else a[cnt++] = -1;// x或y取n的时候取-1
                }
                else if ('0' <= s[i] && s[i] <= '9')
                {
                    int l = 0, shu = 0;
                    for (int j = i; j < strlen(s); j++)
                    {
                        if (s[j] < '0' || s[j]>'9')break;
                        shu = shu * 10 + s[j] - '0';
                        l++;
                    }
                    a[cnt++] = shu;
                    i += (l - 1);//跳过这个数字，免得多次判断这条件。
                }
            }
            if (!sta.empty())//当存在非法F时，不用更新答案。
            {
                continue;
            }
            if (a[2] == -1 && a[3] == -1)ans += 0;//x和y均为n，等价于O(1)
            else if (a[2] != -1 && a[3] == -1) { ans += 1; fu[st.top()] = 1;}//记录复杂度O(n)的变量名
            else if (a[2] != -1 && a[3] != -1 && a[2] > a[3] || (a[2] == -1 && a[3] != -1))//非法F的情况
            {
                int q = st.top(); he[q] = 1;//he数组用来判断什么时候是非法的F
                sta.push(zi);
            }
        }
        if (st.empty())//最后出来的时候再更新一次答案值
        {
            maxx = max(ans, maxx);
            ans = 0;
            memset(b, 0, sizeof b);
        }
        if (st.size())flag = -1;
        if (flag == -1)printf("ERR\n");
        else if (maxx == tmp)printf("Yes\n");
        else printf("No\n");
        //printf("%d %d\n",maxx,ans);
    }
    return 0;
}