[noip2017-提高] 时间复杂度

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

栈式线性扫描：只统计实际进入的『常数→n』循环层数并取最大作指数，死区不贡献但语法照查，输出 Yes/No/ERR。

OJ: roj

题目 ID: 3649

难度:普及+/提高-

标签:模拟栈推导python

创建: 2026-10-02 12:46

更新: 2026-10-10 11:30

形式化题目

每个程序是一棵循环嵌套树，语句按书写顺序执行：

F i x y 打开一层循环并新建变量 $i$ （不可与未销毁的变量重名）： $i$ 从 $x$ 起，满足 $i \leqslant y$ 则执行一轮，随后 $i$ 加 1，直到 $i > y$ 退出；E 关闭一层并销毁该层变量。
边界 $x, y$ 各自为小于 100 的正整数或 $n$ ，且 $n$ 远大于 100； $n$ 是必须保留的规模变量，不能当常数。
每个程序附带一个声称的复杂度：O(1) 或 O(n^w)（ $w$ 为小于 100 的正整数）。
判定三态：程序含语法错误——① F 与 E 不匹配、② 新建变量与未销毁变量重名——则输出 ERR，即使错误位于不会执行的循环体内也算错；否则计算实际复杂度，与声称一致输出 Yes，不一致输出 No。

题面 8 个样例的输出为 Yes Yes ERR Yes No Yes Yes ERR：样例 1 的循环只跑 1 次，是常数复杂度；样例 2 单层“常数 $\to n$ ”为 $O(n^1)$ ；样例 3 只有 F 没有 E，语法错误；样例 4 是二重嵌套的 $O(n^2)$ ；样例 5 是两段独立的一重循环合起来仍为 $O(n)$ ，与声称的 $O(n^2)$ 不符；样例 8 的内外两层重复定义了 x。逐句轨迹见下文思路。

正解

思路

朴素做法是把循环真的执行一遍、数出步数再写成 $\Theta$ 。它从根上不成立： $n$ 没有具体值（只知远大于 100），循环上界无法落地；而且步数本身是 $\Theta(n^w)$ ，规模一大就枚举不动。题目又只要复杂度类别而非步数，所以方向应是——不执行，只分析结构。

第一步：单层循环只有四种可能。 把 $n$ 看成远大于 100 的数，逐一对比 $x$ 与 $y$ ：

$x$	$y$	是否进入	实际次数	复杂度贡献
常数	常数（ $x \leqslant y$ ）	进入	常数次	$O(1)$ ，指数不变
常数	$n$	进入	$n - x + 1$ 次	乘上一个 $n$ ，指数 $+1$
$n$	任意常数	不进入（初值已 $> y$ ）	$0$ 次	体内语句全不执行
$n$	$n$	进入	恰好 $1$ 次	$O(1)$ ，指数不变

四种情况穷尽了 $x, y$ 的取值可能，而只有"常数 $\to n$ "这一种会把复杂度乘上一个 $n$ ——这就是统计的全部依据。

第二步：嵌套加一，顺序取最大。 嵌套循环的次数是内外相乘，对应指数相加，所以维护 depth 记录当前路径上已进入的"常数 $\to n$ "层数即可；顺序执行的多段语句步数相加， $\Theta$ 由最大项决定，于是全程刷新 best = max(depth)，实际复杂度就是 $O(n^{best})$ 。

第三步：死区剪枝。 若某层循环一次都不进入（上表第三种），整个循环体都不执行，体内任何"常数 $\to n$ "循环都不能再贡献指数。用一个 dead 布尔量沿嵌套向下传递：dead = 父层 dead 或 x > y。比较时把 $n$ 换成远大于 100 的占位整数，四种情形便统一成一个比较式（注意 $n$ 对 $n$ 不算 $>$ ，对应恰好进入一次的情形）。

第四步：语法检查与执行无关。 题面明确死代码里的错误也要 ERR，因此查重、配对从不看 dead：F 先查变量是否在存活集合中，在则错误②；然后压栈保存 (depth, 变量名, dead)，再更新统计量。E 若遇到空栈则错误①，否则弹栈恢复三样状态、把变量移出存活集合（销毁后名字可复用）。读完后 err 为真或栈非空（F 未闭合）即 ERR；否则拿 best 与声称的指数比较（O(1) 即指数 0）输出 Yes / No。

下面用两个样例展示 depth / best / dead 随语句的演化（dead=是 时该层对 depth 无贡献，但压栈、弹栈照常发生）：

程序	语句	关键动作	depth	best	说明
样例 6	`F x 9 n`	压栈；常数 $\to n$ ，`depth` $+1$	1	1	正常进入，乘上 $n$
样例 6	`F y n 4`	压栈； $n > 4$ → `dead`，不加	1	1	内层一次不进
样例 6	`E`	弹栈，恢复 `depth=1`、`dead=否`	1	1	死区结束
样例 6	`E`	弹栈，恢复 `depth=0`	0	1	栈空，扫描结束
样例 7	`F y n 4`	压栈； $n > 4$ → `dead`	0	0	最外层就进不去
样例 7	`F x 9 n`	压栈；父层已 `dead`，不加	0	0	本可 $+1$ ，但体不执行
样例 7	`E`	弹栈，恢复外层状态	0	0	语法照常配对
样例 7	`E`	弹栈，恢复 `depth=0`	0	0	栈空，扫描结束

两段的 best 分别为 1 和 0，对应实际复杂度 $O(n^1)$ 与 $O(1)$ ，恰好都与声称一致，输出 Yes。对比可见 dead 的作用域差别：样例 6 死在内层，外层的一次 $+1$ 保留；样例 7 死在外层，内层即使形如"常数 $\to n$ "也不再计数。而重名检查（样例 8）发生在压栈之前、与死活无关，所以照样 ERR。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N_SCALE=1000000;
int bound_val(const string &s){return s=="n"?N_SCALE:atoi(s.c_str());}
string run_program(int lines,string claim, vector<string>&tok, int &pos){ set<string> alive; vector<pair<pair<int,string>, bool> > st; int depth=0,best=0; bool parent_dead=false, err=false; for(int line=0;line<lines;line++){string op=tok[pos++]; if(op=="F"){string var=tok[pos++],x=tok[pos++],y=tok[pos++]; if(err) continue; if(alive.count(var)){err=true; continue;} st.push_back({{depth,var},parent_dead}); bool dead=parent_dead || bound_val(x)>bound_val(y); if(!dead && x!="n" && y=="n"){depth++; best=max(best,depth);} parent_dead=dead; alive.insert(var);} else if(!err){ if(st.empty()){err=true; continue;} depth=st.back().first.first; string var=st.back().first.second; parent_dead=st.back().second; st.pop_back(); alive.erase(var);} } if(err||!st.empty()) return "ERR"; int expected=0; if(claim!="O(1)") expected=atoi(claim.substr(4, claim.size()-5).c_str()); return best==expected?"Yes":"No";}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); vector<string> tok; string s; while(cin>>s) tok.push_back(s); if(tok.empty()) return 0; int pos=0,T=atoi(tok[pos++].c_str()); for(int i=0;i<T;i++){int l=atoi(tok[pos++].c_str()); string claim=tok[pos++]; cout<<run_program(l,claim,tok,pos)<<'\n';} return 0;}

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 12:46
# update_at: 2026-10-02 12:46

import sys
from collections.abc import Iterator

N_SCALE = 10**6  # n 的占位值：n 远大于 100，而正整数边界都小于 100


def bound(token: bytes) -> int:
    """把循环边界换成可比较的整数：n 取大占位值，正整数取原值。"""
    return N_SCALE if token == b"n" else int(token)


def run_program(lines: int, claim: bytes, it: Iterator[bytes]) -> str:
    """按栈语义执行一个程序，比对实际复杂度与声称复杂度，返回 Yes/No/ERR。"""
    alive: set[bytes] = set()                      # 尚未销毁的循环变量
    stack: list[tuple[int, bytes, bool]] = []       # (入栈前层数, 变量名, 入栈前父层是否必不进入)
    depth = 0                                       # 当前已进入的 "常数→n" 循环层数
    best = 0                                        # 历史最大层数，即实际复杂度 O(n^best)
    parent_dead = False                             # 外层必然一次不进：内层一律不贡献复杂度
    err = False

    for _ in range(lines):
        tok = next(it)
        if tok == b"F":
            var, x, y = next(it), next(it), next(it)  # 无论是否已出错都要吃掉整行
            if err:
                continue
            if var in alive:                        # 语法错误②：与存活变量重名
                err = True
                continue
            stack.append((depth, var, parent_dead))
            dead = parent_dead or bound(x) > bound(y)   # 初始值已大于上界：一次都不进
            if not dead and x != b"n" and y == b"n":    # 只有 "常数 → n" 贡献一次幂
                depth += 1
                best = max(best, depth)
            parent_dead = dead
            alive.add(var)
        elif not err:                               # E
            if not stack:                           # 语法错误①：E 没有匹配的 F
                err = True
                continue
            depth, var, parent_dead = stack.pop()   # 弹栈恢复外层状态
            alive.discard(var)

    if err or stack:
        return "ERR"
    expected = 0 if claim == b"O(1)" else int(claim[4:-1])  # 声称的 O(n^w) 指数 w
    return "Yes" if best == expected else "No"


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    T = int(next(data))
    print("\n".join(run_program(int(next(data)), next(data), data) for _ in range(T)))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度： $O(\sum L)$ ，每个程序逐行扫描一次、每行 $O(1)$ ，全程绝不执行循环本身； $t \leqslant 10$ 、 $L \leqslant 100$ 。
空间复杂度： $O(L)$ ，状态栈最深 $L$ 层，存活变量集合至多 $L$ 个元素。

总结

把"执行循环数步数"改写成"分析结构数层数"： $n$ 无具体值、步数指数级，但复杂度类别是静态可算的。
单层只有四种可能，只有"常数 $\to n$ "贡献一次幂； $n$ 初值对常数上界一次不进， $n$ 对 $n$ 恰跑一次。
嵌套 $\to$ 指数相加用 depth，顺序 $\to$ 取最大用 best，死区向内传递用 dead——三个量一趟扫描全部维护。
语法检查独立于执行：存活集合查重、栈查配对，死代码里的错误同样 ERR；三态判断按 ERR → Yes/No 的优先级输出。

题目描述

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

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

F 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”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

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

输入输出格式

输入格式：

输入文件第一行一个正整数 $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： 复制

8 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： 复制

Yes 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掉的P3952或本题的AC记录。

标程展开

复制

// 仅供参考。测试数据由此std生成，如发现std错误请尽快联系管理员

#include 
#include 
#include 
#include 
#include 

using namespace std;

bool stat[26];

inline char t(const string& original) {
	return original[0] - 'a';
}

inline bool isInt(const string& str) {
	return str[0] >= '0' && str[0] <= '9';
}

inline int getPV(const string& str) {
	if(isInt(str)) 
		return atoi(str.c_str());
	else
		return 1000000;
}

struct stackContent {
	int complexity;
	char var;
	bool parentEntryImpossible;
};

int main() {
	int n;
	cin >> n;
	for(int i=1; i<=n; i++) {
		memset(stat, 0, sizeof(stat));

		int lineCnt, expectedComplexity;
		cin >> lineCnt;

		string complexity;
		cin >> complexity;

		if(complexity[2] == '1')
			expectedComplexity = 0;
		else
			sscanf(complexity.c_str(), "O(n^%d)", &expectedComplexity);

		string currentToken, last_t_A; 
		bool validFlag = true;

		int currentComplexity = 0, maxComplexity = 0;
		bool parentEntryImpossible = false;
		stack complexityStack;
		for(int j=1; j<=lineCnt; j++) {
			cin >> currentToken;
			if(currentToken == "F") {
				string t_A, t_B, t_C;
				cin >> t_A >> t_B >> t_C;
				if(!validFlag) continue;

				if(stat[t(t_A)]) {
					validFlag = false;
					continue;
				}

				complexityStack.push((stackContent){currentComplexity, t_A[0], parentEntryImpossible});

				if(parentEntryImpossible)
					parentEntryImpossible = true;
				else if(getPV(t_B) > getPV(t_C))
					parentEntryImpossible = true;
				else if(t_B != "n" && t_C == "n") {
					currentComplexity++;
					maxComplexity = max(maxComplexity, currentComplexity);
				}
				
				stat[t(t_A)] = true;
			} else if(currentToken == "E") {
				if(!validFlag) continue;

				if(complexityStack.size() == 0) {
					validFlag = false;
					continue;
				}

				currentComplexity = complexityStack.top().complexity;
				stat[complexityStack.top().var - 'a'] = false;
				parentEntryImpossible = complexityStack.top().parentEntryImpossible;
				complexityStack.pop();
			}
		}

		if(!validFlag || complexityStack.size() != 0)
			cout << "ERR" << endl;
		else {
			if(maxComplexity == expectedComplexity) 
				cout << "Yes" << endl;
			else
				cout << "No" << endl;
		}
	}

	return 0;
}

[noip2017-提高] 时间复杂度

目录

形式化题目

正解

思路

代码

复杂度

总结