[NOIP 2017 提高组] 时间复杂度

GitHub 跳转原题关系图返回列表

用栈维护循环嵌套、死循环深度和当前有效幂次，线性扫描判断语法并求真实复杂度。

OJ: luogu

题目 ID: P3952

难度:普及+/提高

标签:模拟栈推导noip

日期: 2026-06-20 12:50

题意

给出若干段 A++ 程序，每段程序只包含两种语句：

F i x y
E

你需要先判断程序是否有语法错误；如果没有语法错误，再判断它真正的时间复杂度是否和题目给出的复杂度一致。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXL = 105;

struct Node {
    int type;               // 0: 常数循环, 1: 乘一个 n, 2: 死循环, 3: 根节点
    string var;             // 当前循环变量名
    bool claimed;           // 是否成功占用变量名
    vector<int> children;   // 子循环
};

int test_cnt;
int line_cnt;
string target_complexity;

Node tree[MAXL];
int node_cnt;
int stk[MAXL];
int top_ptr;
bool used_var[256];

int parse_target_power(const string &s) {
    if (s == "O(1)") return 0;
    if (s == "O(n)") return 1;

    int pos1 = s.find('^');
    int pos2 = s.find(')');
    int value = 0;
    for (int i = pos1 + 1; i < pos2; i++) {
        value = value * 10 + (s[i] - '0');
    }
    return value;
}

bool is_n(const string &s) {
    return s == "n";
}

int to_number(const string &s) {
    int value = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        value = value * 10 + (s[i] - '0');
    }
    return value;
}

int get_loop_type(const string &x, const string &y) {
    bool x_is_n = is_n(x);
    bool y_is_n = is_n(y);

    if (!x_is_n && !y_is_n) {
        int lx = to_number(x);
        int ry = to_number(y);
        if (lx > ry) return 2;
        return 0;
    }

    if (!x_is_n && y_is_n) return 1;
    if (x_is_n && !y_is_n) return 2;
    return 0;
}

int dfs_power(int u) {
    if (tree[u].type == 2) return 0;

    int best = 0;
    for (int i = 0; i < (int)tree[u].children.size(); i++) {
        int v = tree[u].children[i];
        best = max(best, dfs_power(v));
    }

    if (tree[u].type == 1) return best + 1;
    return best;
}

int solve_one_case() {
    cin >> line_cnt >> target_complexity;

    memset(used_var, 0, sizeof(used_var));
    node_cnt = 0;
    top_ptr = 1;
    stk[1] = 0;
    tree[0].type = 3;
    tree[0].var = "";
    tree[0].claimed = false;
    tree[0].children.clear();

    bool has_error = false;

    for (int i = 1; i <= line_cnt; i++) {
        string op;
        cin >> op;

        if (op == "F") {
            string var, x, y;
            cin >> var >> x >> y;

            node_cnt++;
            tree[node_cnt].type = get_loop_type(x, y);
            tree[node_cnt].var = var;
            tree[node_cnt].claimed = false;
            tree[node_cnt].children.clear();

            unsigned char name = (unsigned char)var[0];
            if (used_var[name]) {
                has_error = true;
            } else {
                used_var[name] = true;
                tree[node_cnt].claimed = true;
            }

            tree[stk[top_ptr]].children.push_back(node_cnt);
            top_ptr++;
            stk[top_ptr] = node_cnt;
        } else {
            if (top_ptr == 1) {
                has_error = true;
                continue;
            }

            int u = stk[top_ptr];
            if (tree[u].claimed) {
                unsigned char name = (unsigned char)tree[u].var[0];
                used_var[name] = false;
            }
            top_ptr--;
        }
    }

    if (top_ptr != 1) {
        has_error = true;
    }

    if (has_error) return -1;

    int target_power = parse_target_power(target_complexity);
    int real_power = dfs_power(0);
    if (real_power == target_power) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> test_cnt;
    while (test_cnt--) {
        int result = solve_one_case();
        if (result == -1) {
            cout << "ERR\n";
        } else if (result == 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

这份暴力代码把循环嵌套关系建成了一棵树，再递归求整段程序的最高复杂度幂次。它很直观，但其实本题并不需要真的建树。

关键在于先把每层循环分成三类：

常数循环
- 例如 F i 1 10
- 或 F i n n
贡献一个 n 的循环
- 例如 F i 1 n
根本不会执行的死循环
- 例如 F i n 4
- 或 F i 10 3

然后用栈按行扫描整个程序。

扫描时维护三个核心状态：

dead_depth：当前是否处在死循环内部
current_power：当前真实执行路径上的 n 的幂次
max_power：历史上出现过的最大幂次

处理规则是：

遇到 F，先判断变量是否重名，再判断这一层循环属于哪一类；
如果这一层是死循环，就让 dead_depth++；
如果这一层是 $O(n)$ 循环，且当前 dead_depth == 0，那么它真的会让复杂度多乘一个 n；
遇到 E 时，再把这一层的状态弹掉并回退。

最后：

若 F/E 不匹配，或者变量重名，输出 ERR
否则比较 max_power 和目标复杂度的幂次是否相同

代码

cpp

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241#include <bits/stdc++.h>
using namespace std;

/**
 * ============================================================
 * 题目: P3952 [NOIP 2017 提高组] 时间复杂度
 * ============================================================
 * 核心任务: 判断小明声称的"时间复杂度"是否正确
 *
 * 【A++ 循环语法】
 *   F i x y    // 新建变量 i = x, 当 i <= y 时进入循环, 每次 i++
 *     循环体
 *   E          // 循环结束, 变量 i 被销毁
 *
 * 【核心思想】
 * 用栈模拟循环的嵌套关系。每个循环属于三类之一：
 *   0: 常数循环 (数字->数字且x<=y, 或 n->n)
 *   1: 贡献 O(n) 的循环 (数字->n)
 *   2: 死循环 (数字->数字且x>y, 或 n->数字)
 *
 * 关键观察: 如果一个循环是"死循环"(类型2), 那么它内部的所有循环
 * 实际上都不会执行。因此需要一个计数器 dead_depth 来屏蔽内部贡献。
 *
 * 【ERR 语法错误】
 * ① F 和 E 不匹配
 * ② 变量名与已存在且未被销毁的变量重复
 * 注意: 即使循环不会执行, 内部语法错误也要报 ERR!
 * ============================================================
 */

const int MAXL = 105;

/**
 * 【LoopInfo: 每一层循环需要记录的信息】
 * 为什么需要这些信息? 因为出栈(E)时需要回退各种状态。
 */
struct LoopInfo {
    string var;       // 当前循环定义的变量名
    bool claimed;     // 这个变量名是否成功占用
                      // (如果 F 时发现变量名重复, claimed=false, 出栈时不应释放)
    bool is_dead;     // 这一层循环是否一开始就不会执行 (类型2)
    bool add_power;   // 这一层是否真的让复杂度多乘了一个 n
};

int test_cnt;         // 数据组数
int line_cnt;         // 当前程序的行数
string target_complexity; // 小明声称的复杂度字符串

bool used_var[256];   // 变量名占用表。下标用 ASCII 码, 值表示是否被占用
                      // 题目保证变量名是单个小写字母(不为n), 所以256够用了
LoopInfo stk[MAXL];   // 栈, 模拟循环嵌套
int top_ptr;          // 栈顶指针, 同时表示栈中元素个数

/**
 * 【解析声称的复杂度字符串, 提取指数】
 * 输入: "O(1)" -> 返回 0
 *       "O(n^2)" -> 返回 2
 * 方法: 先处理两个特殊短串, 再找 '^' 和 ')' 之间的数字
 */
int parse_target_power(const string &s) {
    if (s == "O(1)") return 0;
    if (s == "O(n)") return 1;

    int pos1 = s.find('^');
    int pos2 = s.find(')');
    int value = 0;
    for (int i = pos1 + 1; i < pos2; i++) {
        value = value * 10 + (s[i] - '0');
    }
    return value;
}

/**
 * 【判断字符串是否为 "n"】
 */
bool is_n(const string &s) {
    return s == "n";
}

/**
 * 【把纯数字字符串转成整数】
 * 注意: 调用前要确保 s 不是 "n"
 */
int to_number(const string &s) {
    int value = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        value = value * 10 + (s[i] - '0');
    }
    return value;
}

/**
 * 【判断循环类型: 根据 x 和 y 的形式分类】
 * 返回值:
 *   0 -> 常数循环 (执行常数次或1次)
 *   1 -> 这一层会贡献一个 n (数字 -> n)
 *   2 -> 死循环, 根本不会执行 (数字>数字 或 n->数字)
 */
int get_loop_type(const string &x, const string &y) {
    bool x_is_n = is_n(x);
    bool y_is_n = is_n(y);

    if (!x_is_n && !y_is_n) {
        // 数字 -> 数字
        int lx = to_number(x);
        int ry = to_number(y);
        if (lx > ry) return 2;  // 起点>终点, 循环不执行
        return 0;               // 执行 (ry-lx+1) 次, 常数级别
    }

    if (!x_is_n && y_is_n) return 1;  // 数字 -> n: O(n)
    if (x_is_n && !y_is_n) return 2;  // n -> 数字: n远大于数字, 不执行

    // n 到 n 只执行 1 次, 是常数循环。
    return 0;
}

/**
 * 【处理一个完整的程序, 返回结果编码】
 * 返回值:
 *   -1 -> 语法错误 ERR
 *    1 -> 复杂度匹配 Yes
 *    0 -> 复杂度不匹配 No
 */
int solve_one_case() {
    cin >> line_cnt >> target_complexity;

    // 初始化: 清空变量占用表, 清空栈
    memset(used_var, 0, sizeof(used_var));
    top_ptr = 0;

    int target_power = parse_target_power(target_complexity);

    /**
     * 【三个核心状态变量】
     * current_power: 当前"活跃执行路径"上的 O(n) 层数
     *   - 如果当前在死循环内部, 新增的普通循环不会增加 current_power
     * max_power: 历史上出现过的最大层数 (最终要和 target_power 比较)
     * dead_depth: 当前嵌套在多少个"死循环"内部
     *   - dead_depth > 0 时, 内部的新循环对复杂度无贡献
     */
    int current_power = 0;
    int max_power = 0;
    int dead_depth = 0;
    bool has_error = false;

    for (int i = 1; i <= line_cnt; i++) {
        string op;
        cin >> op;

        if (op == "F") {
            // === 处理 F i x y ===
            string var, x, y;
            cin >> var >> x >> y;

            bool claimed = false;
            unsigned char name = (unsigned char)var[0];

            // 【语法检查②: 变量名是否与已存在的重复】
            if (used_var[name]) {
                has_error = true; // 未销毁变量重名
            } else {
                used_var[name] = true;  // 占用该变量名
                claimed = true;         // 标记为"我成功占用了"
            }

            int loop_type = get_loop_type(x, y);

            // 入栈: 把这一层循环的信息记录下来
            top_ptr++;
            stk[top_ptr].var = var;
            stk[top_ptr].claimed = claimed;
            stk[top_ptr].is_dead = false;
            stk[top_ptr].add_power = false;

            if (loop_type == 2) {
                // === 死循环: 标记这一层, dead_depth 增加 ===
                stk[top_ptr].is_dead = true;
                dead_depth++;
            } else if (loop_type == 1 && dead_depth == 0) {
                // === O(n) 循环, 且当前不在任何死循环内部 ===
                // 只有这时, 这一层才真的会让复杂度多乘一个 n
                stk[top_ptr].add_power = true;
                current_power++;
                if (current_power > max_power) {
                    max_power = current_power;  // 更新历史最大值
                }
            }
            // 类型 0 (常数循环): 什么都不做
        } else {
            // === 处理 E ===
            if (top_ptr == 0) {
                // 栈已空却有 E -> F 和 E 不匹配 (语法错误①)
                has_error = true;
                continue;
            }

            // 弹栈前回退该层造成的所有状态变化
            if (stk[top_ptr].is_dead) {
                dead_depth--;       // 退出一个死循环
            }
            if (stk[top_ptr].add_power) {
                current_power--;    // 退出一个 O(n) 循环
            }
            if (stk[top_ptr].claimed) {
                // 只有我成功占用了变量, 才需要在退出时释放
                unsigned char name = (unsigned char)stk[top_ptr].var[0];
                used_var[name] = false;
            }
            top_ptr--;  // 真正弹栈
        }
    }

    // 处理完所有行后, 如果栈非空 -> 有 F 没配对的 E
    if (top_ptr != 0) {
        has_error = true;
    }

    if (has_error) return -1;
    if (max_power == target_power) return 1;
    return 0;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> test_cnt;
    while (test_cnt--) {
        int result = solve_one_case();
        if (result == -1) {
            cout << "ERR\n";
        } else if (result == 1) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

参考代码（详细注释版）

下面这份代码来自 Rainboy，保留了大量中文注释，适合教学中逐行理解“栈维护嵌套深度”和“循环分类”的核心思想：

cpp

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313//Author by [Rainboy](https://github.com/rainboylvx)
//date: 2024-07-23 09:44:20

/**
 * ============================================================
 * 题目: P3952 [NOIP 2017 提高组] 时间复杂度
 * ============================================================
 * 核心任务: 判断小明给出的"时间复杂度"是否正确
 *
 * 【A++ 循环语法】
 *   F i x y    // 新建变量 i = x, 当 i <= y 时进入循环, 每次 i++
 *     循环体
 *   E          // 循环结束, 变量 i 被销毁
 *
 * 【时间复杂度的计算规则】
 *   我们把每一层循环对复杂度的贡献看作 "n 的指数":
 *   - 数字 -> 数字 (x <= y): 循环执行常数次, 贡献指数 0
 *   - 数字 -> 数字 (x > y) : 循环不执行, 贡献指数 0
 *   - 数字 -> n            : 循环执行约 n 次, 贡献指数 1
 *   - n -> 数字            : n 远大于数字, 循环不执行, 贡献指数 0
 *   - n -> n               : 循环执行常数次, 贡献指数 0
 *
 *   嵌套循环的总指数 = 各层指数之和 (栈顶存的就是当前嵌套深度的总指数)
 *
 * 【ERR 语法错误】
 *   ① F 和 E 不匹配 (括号不匹配)
 *   ② 变量名与已存在且未被销毁的变量重复
 *   注意: 即使循环不会执行, 里面的语法错误也要报 ERR!
 * ============================================================
 */

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+5;
int n,m;
string s;
int T;                          // 数据组数

int max_time  = 0;              // 当前程序实际的最大时间复杂度指数
bool err_flag = 0;              // 标记是否发现语法错误
int read_line_cnt = 0;          // 当前程序还剩多少行没读

/**
 * 【手工栈 my_sta】
 * 为什么用栈? 循环允许嵌套, 后进先出(F 是入栈, E 是出栈)
 * 栈中每个元素存储: "从外层到当前层, 累计贡献的 n 的指数"
 * 例如: 第一层贡献 1, 第二层贡献 1, 栈顶就是 2 (表示当前在 n^2 的循环内)
 */
struct my_sta {
    int a[maxn];    // 栈的底层数组
    int idx = 0;    // 栈顶指针(同时表示栈的大小)

    void clear() { idx = 0;}                // 清空栈
    void push(int v) { a[idx++] = v;}       // 压栈: 当前层总指数 = v
    void pop() {--idx;}                     // 弹栈: 当前循环结束
    int size() {return idx;}                // 栈中元素个数
    bool empty() { return idx == 0;}        // 判空
    int top() { return a[idx-1];}           // 取栈顶(当前嵌套深度的总指数)
    int atop() {
        if( empty() ) return 0;             // 空栈说明没有外层循环, 指数为 0
        return top();
    }
} sta;

/**
 * 【变量名池 bct】
 * 作用: 记录当前所有"活着"的变量名, 用于检测变量名重复
 * 规则: 进入一个 F 就把变量名加入数组, 遇到 E 就把当前层变量名移除
 * 为什么不直接 map/set? 题目数据量小(L<=100), 数组遍历就够用了
 */
int cnt;                        // 当前活着的变量个数
string bct[maxn];               // 活着的变量名列表

void push_str(const string &s ) {
    bct[cnt++] = s;             // 新变量加入"存活名单"
}
void pop_str() {
    cnt--;                      // 最内层循环结束, 对应变量"销毁"
}
bool find_str(const string & s) {
    // 遍历当前所有存活变量, 看名字 s 是否已被占用
    for(int i = 0;i < cnt ;++i )
    {
        if( bct[i] == s) return 1;  // 找到重复, 返回 true
    }
    return 0;                       // 没找到, 名字可用
}


bool with_n = 0;                // 小明声称的复杂度是否包含 n (O(n^w) 为 1, O(1) 为 0)
int _time;                      // 小明声称的指数 w (O(1) 时为 0)

/**
 * 【解析小明声称的复杂度】
 * 输入样例: "O(1)" 或 "O(n^2)"
 * 目标: 提取出 with_n(是否含n) 和 _time(指数是多少)
 */
void time_complex(){
    cin >> s;
    int l = s.length();
    with_n = 0;
    _time = 0;

    // 第一遍扫描: 看字符串里有没有字母 'n'
    for(int i =0; i < l;i++)
        if(s[i] == 'n') {
            with_n = 1;         // 说明是 O(n^w) 形式
            break;
        }

    // 第二遍扫描: 提取数字 (连续的), 就是指数 w
    for(int i =0; i < l;i++)
    {
        if( s[i] >='0' && s[i] <= '9' )
        {
            int t = s[i] - '0';
            _time *= 10;
            _time += t;
        }
    }
    // 如果输入是 O(1), 上面提取不到数字, _time 保持 0, with_n 也是 0
}

/**
 * 【把字符串解析成数字, 或识别为 n】
 * 返回值:
 *   -1  -> 字符串是 "n"
 *   >=0 -> 字符串表示的正整数
 */
int get_n_number(const string & s) {
    if( s[0] == 'n') return -1;     // 特殊标记: 这个是 n, 不是数字
    int n = 0;
    for(int i = 0 ;i< s.length() ;i++) {
        n *=10;
        n += s[i] -'0';
    }
    return n;
}


/**
 * 【快速跳过一段"不执行的循环体"】
 * 什么时候用? 当发现循环条件满足 "n -> 数字" 时, 循环不会执行。
 * 虽然循环不执行, 但输入里对应的 F...E 还是要读完, 否则后面的数据会错位。
 * 方法: 用 e_cnt 计数, F 使计数+1, E 使计数-1, 计数回到 1 时跳出。
 * (进来时已经读了 1 个 F, 所以初始 e_cnt=1)
 */
void read_until_e() {
    int e_cnt = 1;              // 当前还有 e_cnt 层循环没配对
    string var ,x,y;
    while(1) {
        cin >> var;
        if( var == "E") {
            read_line_cnt--;    // 消耗一行
            if( e_cnt == 1) break;  // 正好配对到当前这层的 E
            e_cnt--;            // 是内层循环的 E
        }
        else { // 只可能是 for (F)
            cin >> var >> x >> y;
            read_line_cnt--;    // 消耗一行
            e_cnt++;            // 又嵌套了一层
        }
    }
}


/**
 * 【处理一行 F i x y】
 * 这是整个题目的核心逻辑:
 * 1. 读取变量名 var, 起点 s, 终点 t
 * 2. 检查变量名是否重复 (语法错误②)
 * 3. 根据 x,y 的类型判断循环是否贡献指数
 * 4. 维护栈和 max_time
 */
void deal_f() {
    string var,s,t;
    cin >> var >> s >> t;       // 读入: 变量名, 起点, 终点

    int x = get_n_number(s);    // x: 起点对应的数值, -1 表示 n
    int y = get_n_number(t);    // y: 终点对应的数值, -1 表示 n

    // === 语法检查: 变量名是否与已存活的变量重复 ===
    bool _find = find_str(var);
    if( _find ) {
        err_flag = 1;           // 发现重复变量, 标记错误
    }

    // k = 当前外层循环贡献的总指数 (栈顶)
    int k = sta.atop();

    /**
     * 【情况分类讨论】
     * 用 x,y 是否为 -1(即 n) 来分类:
     */

    if( x == -1 && y == -1) {
        // === 情况1: n -> n ===
        // n 到 n, 只执行 1 次, 常数级别, 指数不增加
        push_str(var);          // 变量加入存活名单
        sta.push(k + 0);        // 总指数 = 外层指数 + 0
    }
    else if( x !=-1 && y != -1 ){
        // === 情况2: 数字 -> 数字 ===
        // 无论 x <= y 还是 x > y, 对复杂度指数的贡献都是 0
        // (x>y 时不进入循环, x<=y 时常数次循环)
        push_str(var);
        sta.push(0 + k);        // 总指数不变
    }
    else {
        // === 情况3: 有一个是 n ===
        if( x == -1) {
            // === 情况3a: n -> 数字 ===
            // n 远大于任何输入数字, 所以循环条件一开始就不成立
            // 循环体**一次都不执行**
            // 因为不执行, 当前这层不需要入栈, 但要跳过整个循环体
            read_until_e();     // 把对应的 F...E 全部读完
        }
        else{
            // === 情况3b: 数字 -> n ===
            // 循环约执行 n 次, 贡献指数 +1
            push_str(var);
            sta.push(1 + k);    // 总指数 = 外层指数 + 1
        }
    }

    // 更新当前程序的最大指数 (用于和声称的复杂度比较)
    max_time = max(max_time,sta.atop());
}

/**
 * 【处理一行 E】
 * E 表示最内层循环结束:
 * - 弹栈 (该层对复杂度的贡献结束)
 * - 销毁该层对应的变量名
 */
void deal_e() {
    if( sta.empty()) {
        // 栈已经空了, 却来了个 E -> F 和 E 不匹配 (语法错误①)
        err_flag = 1;
    }
    else {
        sta.pop();              // 弹出当前层复杂度指数
        pop_str();              // 销毁当前层变量
    }
}

/**
 * 【读取并处理一个完整的程序】
 * 流程:
 * 1. 读 L (行数) 和声称的复杂度
 * 2. 逐行读取 F 或 E, 调用对应处理函数
 * 3. 读完所有行后检查栈是否为空 (F 和 E 是否完全匹配)
 * 4. 输出 Yes / No / ERR
 */
void read_one_data() {
    cin >> n;
    read_line_cnt = n;          // 这个程序共有 n 行

    time_complex();             // 解析声称的复杂度 -> with_n, _time

    while( read_line_cnt > 0)   // 逐行处理
    {
        read_line_cnt--;
        cin >> s;
        if( s[0] == 'F') {
            deal_f();           // 进入循环
        }
        else if( s[0] == 'E') {
            deal_e();           // 退出循环
        }
    }

    // 处理完后, 如果栈非空 -> 有 F 没配对的 E, 语法错误①
    if( !sta.empty()) err_flag = 1;

    // === 输出结果 ===
    if( err_flag ) {
        cout << "ERR\n";        // 只要有语法错误, 不管复杂度对不对都输出 ERR
    }
    else {
        // 比较实际复杂度 max_time 和声称复杂度 _time
        if( max_time ==  0 && with_n == 0) {
            // 实际 O(1), 声称 O(1) -> Yes
            std::cout << "Yes"<< "\n";
        }
        else if( max_time != 0 && with_n == 1 ) {
            // 实际含 n, 声称也含 n, 比较指数是否相等
            if( max_time == _time )
                std::cout << "Yes"<< "\n";
            else
                std::cout << "No"<< "\n";
        }
        else {
            // 一个 O(1) 一个 O(n^w), 肯定不一样
            std::cout << "No"<< "\n";
        }
    }
}

int main (int argc, char *argv[]) {
    std::cin >> T;
    while (T--) {
        // 每组数据前, 重置所有全局状态!
        sta.clear();            // 清空栈
        max_time = 0;           // 最大指数归零
        err_flag = 0;           // 错误标记归零
        cnt=0;                  // 存活变量数归零
        read_line_cnt = 0;      // 剩余行数归零
        read_one_data();
    }

    return 0;
}

两份参考代码的对比

目录里同时放了两份带注释的实现，核心思路相同（都用栈模拟循环嵌套、都按 x 和 y 的类型分类讨论），但实现细节有差异：

对比维度	`main.cpp`	`main-rainboy.cpp`
死循环处理	死循环也入栈，用 `dead_depth` 计数屏蔽内部贡献	用 `read_until_e()` 直接跳过死循环体，不入栈
死循环内语法检查	✅ 逐行处理，能发现内部变量重复	⚠️ 跳过时不检查，可能漏报 ERR
变量查重	`used_var[256]`，O(1)	`bct[]` 数组线性遍历，O(n)
复杂度统计	`current_power` 和 `max_power` 分开维护	栈顶直接存累计指数

关键差异在于死循环内的语法错误处理。

题目明确说明：

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

main-rainboy.cpp 的 read_until_e() 只是机械地把死循环体内的输入读掉、不做任何变量名重复检查。如果死循环内部出现了变量名重复（例如 F i n 4 里面又写了一个 F i 1 1），这份代码会误判为 Yes/No 而非 ERR。

main.cpp 即使遇到死循环，也会把每一行 F 都入栈并检查 used_var，因此不会漏掉内部的语法错误。

💡 学习建议：先看 main.cpp 理解"死循环也要入栈、用 dead_depth 屏蔽"的严谨做法；再看 main-rainboy.cpp 作为另一种思维角度的补充。

复杂度

每组程序只需要线性扫描一次，所以时间复杂度是 $O(L)$ ，空间复杂度也是 $O(L)$ 。

总结

这题真正的关键不是“复杂度公式”，而是把循环语义先分清楚：

哪些循环是常数层
哪些循环会贡献一个 n
哪些循环根本不会执行

一旦这三类分清楚，再用栈维护嵌套和死循环屏蔽关系，整题就是标准线性模拟。

P3952 [NOIP 2017 提高组] 时间复杂度

题目背景

NOIP2017 提高组 D1T2

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++ 语言的循环结构如下：

cpp

1
2
3F i x y
    循环体
E

其中F i x y表示新建变量 $i$ （变量 $i$ 不可与未被销毁的变量重名）并初始化为 $x$ ，然后判断 $i$ 和 $y$ 的大小关系，若 $i$ 小于等于 $y$ 则进入循环，否则不进入。每次循环结束后 $i$ 都会被修改成 $i+1$ ，一旦 $i$ 大于 $y$ 终止循环。

$x$ 和 $y$ 可以是正整数（ $x$ 和 $y$ 的大小关系不定）或变量 $n$ 。 $n$ 是一个表示数据规模的变量，在时间复杂度计算中需保留该变量而不能将其视为常数，该数远大于 $100$ 。

E 表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母 $\operatorname O$ 表示通常意义下 $\Theta$ 的概念。

输入格式

输入文件第一行一个正整数 $t$ ，表示有 $t$ （ $t \le 10$ ）个程序需要计算时间复杂度。每个程序我们只需抽取其中 F i x y 和 E 即可计算时间复杂度。注意：循环结构允许嵌套。

接下来每个程序的第一行包含一个正整数 $L$ 和一个字符串， $L$ 代表程序行数，字符串表示这个程序的复杂度，O(1) 表示常数复杂度，O(n^w) 表示复杂度为 $n^w$ ，其中 $w$ 是一个小于 $100$ 的正整数，输入保证复杂度只有 O(1) 和 O(n^w) 两种类型。

接下来 $L$ 行代表程序中循环结构中的F i x y或者 E。程序行若以F开头，表示进入一个循环，之后有空格分离的三个字符（串）i x y，其中 $i$ 是一个小写字母（保证不为 $n$ ），表示新建的变量名， $x$ 和 $y$ 可能是正整数或 $n$ ，已知若为正整数则一定小于 $100$ 。

程序行若以E开头，则表示循环体结束。

输出格式

输出文件共 $t$ 行，对应输入的 $t$ 个程序，每行输出 Yes 或 No 或者 ERR，若程序实际复杂度与输入给出的复杂度一致则输出 Yes，不一致则输出 No，若程序有语法错误（其中语法错误只有: ① F 和 E 不匹配 ②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出 ERR。

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

输入输出样例 #1

输入 #1

text

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
348
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

输出 #1

text

1
2
3
4
5
6
7
8Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明/提示

【输入输出样例解释 $1$ 】

第一个程序 $i$ 从 $1$ 到 $1$ 是常数复杂度。

第二个程序 $x$ 从 $1$ 到 $n$ 是 $n$ 的一次方的复杂度。

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环， $n$ 的平方的复杂度。

第五个程序两个一重循环， $n$ 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为 $n$ 远大于 $100$ ， $100$ 大于 $4$ ）。

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量 $x$ 与第一重循环中的变量重复，出现语法错误②，输出 ERR。

【数据规模与约定】

对于 $30\%$ 的数据：不存在语法错误，数据保证小明给出的每个程序的前 $L/2$ 行一定为以 F 开头的语句，第 $L/2+1$ 行至第 $L$ 行一定为以 E 开头的语句， $L \le 10$ ，若 $x$ 、 $y$ 均为整数， $x$ 一定小于 $y$ ，且只有 $y$ 有可能为 $n$ 。

对于 $50\%$ 的数据：不存在语法错误， $L \le 100$ ，且若 $x$ 、 $y$ 均为整数， $x$ 一定小于 $y$ ，且只有 $y$ 有可能为 $n$ 。

对于 $70\%$ 的数据：不存在语法错误， $L \le 100$ 。

对于 $100\%$ 的数据： $L \le 100$ 。

如果需要 Hack 请私信 @zhouyonglong 或发讨论，提供数据和能 Hack 掉的本题的AC记录。