【题解】NOIP2017 时间复杂度 | 洛灵酱的小窝

洛灵酱的小窝

闻道有先后，术业有专攻。

0%

【题解】NOIP2017 时间复杂度

发表于 更新于 分类于 Valine：

题目链接

蒟蒻调了三个小时的代码终于把这题AC了qwq。

这题值得注意的几个点有：

  1. E也有可能有多余导致ERR。
  2. 每遇到一个E都必须清理到前一个F语句的变量名。

另外：

  1. sscanf可以很方便的格式化字符串到另一个要存储的数据里面去。
  2. 程序输入的每行代码可以使用结构体保存，而一段程序可以使用队列，但是STL提供的队列好像不能满足我们的要求，于是我们选择vector。
  3. 判断是否每个F都可以对上一个E使用栈可以很方便的解决。

剩下的慢慢调试就好了qwq。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;

//#define DEBUG

int T;

struct Line {
    char op, i;
    int x, y;
    bool disable;
};

int main() {
    #ifdef DEBUG
    freopen("P3952.in", "r", stdin);
    #endif

    cin >> T;
    while (T--) {
        int L, reqO = 0, resO = 0;
        string O;
        cin >> L >> O;
        if (O != "O(1)")
            sscanf(O.c_str(), "O(n^%d)", &reqO);

        vector<Line> que;
        for (int i = 1; i <= L; i++) {
            char op;
            cin >> op;
            if (op == 'F') {
                char i;
                string tmp1, tmp2;
                cin >> i >> tmp1 >> tmp2;
                int x = (tmp1 == "n" ? 101 : stoi(tmp1));
                int y = (tmp2 == "n" ? 101 : stoi(tmp2));
                que.push_back(Line{'F', i, x, y, 0});
            } else if (op == 'E') {
                que.push_back(Line{'E', 0, 0, 0, 0});
            }
        }

        int err = 0, tmpO = 0;
        map<char, bool> var;
        stack<char> op;
        Line nowLine, lastLine = {'F', 0, 0, 101, 0};
        for (auto k = que.begin(); k != que.end(); k++) {
            nowLine = *k;

            if (nowLine.op == 'F') {
                op.push('F');

                if (!var[nowLine.i]) var[nowLine.i] = 1;
                else { err = 1; break; }

                if (!nowLine.disable) {
                    if (nowLine.x <= nowLine.y) {
                        if (nowLine.y == 101 && nowLine.x != 101) {
                            stack<char> st;
                            st.push('F');
                            auto p = k + 1;
                            tmpO++;
                            while (!st.empty() && p != que.end()) {
                                if (p->op == 'E') {
                                    resO = max(resO, tmpO);
                                    st.pop();
                                    tmpO--;
                                } else {
                                    st.push('F');
                                    if (p->x > p->y) break;
                                    if (p->y == 101 && p->x != 101) tmpO++;
                                    p->disable = 1;
                                }
                                p++;
                            }

                            resO = max(resO, tmpO);
                            tmpO = 0;
                        }
                    } else {
                        nowLine.disable = 1;
                        stack<char> st;
                        st.push('F');
                        for (auto p = k; p != que.end(); p++) {
                            if (st.empty()) break;
                            if (p->op == 'F') {
                                st.push('F');
                                p->disable = 1;
                            } else if (st.top() == 'F') {
                                st.pop();
                            }
                        }
                    }
                }
            } else {
                if (op.empty()) { err = 1; break; }
                if (op.top() == 'F') op.pop();
                for (auto p = k; p >= que.begin(); p--) {
                    if (p->op == 'F' && var[p->i]) var[p->i] = 0;
                }
            }

            lastLine = nowLine;
        }

        if (err || !op.empty()) {
            cout << "ERR" << endl;
        } else if (resO == reqO) {
            cout << "Yes" << endl;
        } else {
            #ifdef DEBUG
            cout << "No: " << resO << endl;
            #else
            cout << "No" << endl;
            #endif
        }
    }

    return 0;
}