题解 P3952 【时间复杂度】

2019 年 09 月 06 日

1805 次浏览

1999字数

作为一名蒟蒻，竟然有胆量打开[这道蓝题](https://www.luogu.org/problem/P3952)（主要是教练让做的qwq）
不过看题看下来没有特别难的语法/算法点，主要是要细心地模拟，考虑到每一种情况。
输入怎么处理呢？Θ$_0$ 怎么得到呢？
在输入时我们可以直接只储存string类型的复杂度数值
一层一层的循环嵌套就可以用栈来模拟——遇到“F”即进栈，但是同时要记录此时的这一层复杂度增不增加，这一层能不能进去，等等等等。
（具体注释中有详细解释，包括我调试时的输出测试等等）
我最后用stringstream将我求得得int类型的复杂度转成了string，通过他与最初输入截取获得的小明算的复杂度进行对比（这里好像不写函数也可以，但是我正好有写好的就复制过来了）

（其实还有一种方法——将最初获得的string类型的复杂度用atof函数转成float类型再比较）
atof函数将string类型转为float类型的格式：

```cpp
string s = "12345";
atof(s.c_str()); //如果是一个char类型数组直接放上数组名就可以了
```

题目代码：

```cpp
#include<iostream>
#include<string>
#include<stack>
#include<map>
#include<sstream>

using namespace std;

struct state
{
    bool k; //能不能进去 
    bool cs; //是不是常数项 
    int o;
    map <char, bool> mi;
    void ini()
    {
        k = true;
        o = 0;
        mi.clear();
        cs = true;
    }
};

stack <state> st;

int cmps(string a, string b)
{
    if(a.size()>b.size()||(a.size()==b.size()&&a>b)) return 1;
    if(a.size()==b.size()&&a==b) return 0;
    return -1;
}

int main()
{
    int n;
    cin >> n;
    for(int di = 0; di < n; di++)
    {
        int l;
        string o0s;
        cin >> l >> o0s;
        if(o0s.size() > 4) o0s = o0s.substr(4, o0s.size() - 5);
        else o0s = "0";
        char s1, s2;
        string s3, s4;
        int maxo = 0;
        bool err = false; //判断是否有语法错误 
        //bool t = true; //是否进入F
        while(!st.empty()) st.pop();
        for(int i = 0; i < l; i++)
        {
            cin >> s1;
			state F;
            if(s1 == 'F') //F开始 
            {
                F.ini();
                if(!st.empty()){
					F.o = st.top().o;
					F.mi = st.top().mi;
					F.k = st.top().k;
				}
                cin >> s2 >> s3 >> s4;
                if(s3 == "n" && s4 != "n") //F循环参数x为n 
                {
                    F.k = false; //x=n>>y 循环不进入 
                }
                if(F.mi[s2] == true) //如果i被上层F循环用过 
                {
                    err = true;
                    //cout << "i被上层F循环用过 ";
                }
                F.mi[s2] = true; //标记i已用过 
                if(s4 == "n") //y为n 
                {	
					if(s3 != "n")
                    if(F.k != false) //F循环可进入 
                    F.o++; //进入F循环，复杂度增加一次 
                }
                if(s3 != "n" && s4 != "n" && cmps(s3,s4) == 1) //如果x比y大 
                {
                    F.k = false; //接下来的F循环不进入
                }
                st.push(F);
                //cout << "PUSH" << endl;
            }
            if(s1 == 'E') //结束上层F循环 
            {
                if(st.empty()) //如果上面没有对应的E 
                {
                    err = true; //语法必定错误 
                    //cout << "上面没有对应的E ";
                }
                else
                {
					
					maxo = max(maxo, F.o);
                	st.pop();
                	//cout << "POP" << endl;
            	}
            }
            //cout << "for end"  << endl;
        }
        if(!st.empty()) //如果在所有循环结束后还有剩余的E 
        {
            err = true;
            //cout << "在所有循环结束后还有剩余的E";
        }
        if(!err)
        {
            stringstream ss;
            ss << maxo;
            string os;
            ss >> os;
            if(cmps(os, o0s) == 0) cout << "Yes";
            else cout << "No";
        }
        else cout << "ERR"; 
        //cout << endl << "*********" << maxo <<  " " << o0s << "*********";
        cout<< endl;
    }
    return 0;
}
```