题解 P3952 【时间复杂度】

杨戬大师 · 2019-08-28 21:49:18 · 题解

根据 F 和 E 想到用栈（stack）来模拟。

每一次如果会加一个指数级别，就向栈里面压入个 1；

如果只是常数级别的，就压入一个 0；

如果直接来一个无法继续的（如for (i = 1; i < 1; i++)），就压入一个 -1。

每一次都把栈里面的所有 0 和 1 都加起来，就是o(n^m)中的那个指数m（m==0即为o(1)），但是遇到了 -1 就把计数器归零，因为 -1 后面的都不可能走到了。因为栈是first in last out，所以每次加top是倒着加的，所以可以采用如上模拟的方法。

AC代码：

#include <iostream>
#include <cstring>
#include <string>
#include <stack>

using namespace std;

stack <int> s;
int main()
{
    int t, L, f1, f2, fs, es, lx, ly, ls, rf[10005], i, j, k;
    char co, c1, cf, cp, c2, cfe, x1, y1;
    string ij, x, y;
    bool errj;
    cin >> t;
    for (k = 1; k <= t; k++)//多组测试数据 
    {
        fs = 0;//初始化阶段 
        es = 0;
        f2 = 0;
        memset(rf, 0, sizeof(rf));
        x = "";
        y = "";
        ij = "";
        errj = false;
        while (!s.empty())
            s.pop();
        cin >> L >> co >> c1 >> cf;//开始输入 
        if (cf == '1')//顺便计算复杂度 
            f1 = 0;
        else
            cin >> cp >> f1;//输入 
        cin >> c2;
        for (i = 1; i <= L; i++)//每组测试数据中的程序的L 
        {
            cin >> cfe;//输入 
            if (cfe == 'E')
            {
                es++;
                if (!s.empty())
                    s.pop();
                else
                    errj = true;
                continue;
            }
            fs++;
            ls = s.size();
            cin >> ij[ls];
            for (j = 0; j < ls; j++)//判断变量是否有重复 
                if (ls != 0 && ij[j] == ij[ls])
                {
                    errj = true;
                    break;
                }
            cin >> x >> y;//最后输入 
            lx = x.size();
            ly = y.size();
            if (x[0] != 'n' && y[0] != 'n' && (lx > ly || lx == ly && x > y) || x[0] == 'n' && y[0] != 'n')
                s.push(-1);
            else
            {
                if (x[0] != 'n' && y[0] == 'n')
                    s.push(1);
                else
                    s.push(0);
            }
            ls = s.size();
            rf[0] = 0;
            for (j = 1; j <= ls; j++)
            {
                rf[j] = s.top();
                rf[0] += rf[j];
                if (rf[j] == -1)
                    rf[0] = 0;
                s.pop();
            }
            for (j = ls; j > 0; j--)
                s.push(rf[j]);
            f2=max(f2, rf[0]);
        }
        if (errj || fs != es)
            cout << "ERR";
        else
        {
            if (f1 == f2)
                cout << "Yes";
            else
                cout << "No";
        }
        if (k < t)//换行 
            cout << endl;
    }
    return 0;
}

成功解出此题的关键，就是想到用栈，这其实也很好想。然后，再细心的模拟就行了。注意stack空的时候访问

s.size() , s.top()

会RE，一定要注意！