[NOIP2017 提高组] 时间复杂度

题目背景

NOIP2017 提高组 D1T2

题目描述

小明正在学习一种新的编程语言 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$ 表示通常意义下 $\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

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

解题思路

• 模拟。

Code

#include<cstdio>
#include<vector>
#include<string>
#include <iostream>
#include <map>
#include <stack>
#include<sstream>

using namespace std;

int l;
string o;

void solve() {
	// 输入数据
	cin >> l >> o;
	map<char, bool> vis;
	string s;
	cin.ignore();
	vector<string> a;
	for (int i = 1; i <= l; i++) {
		getline(cin, s);
		a.push_back(s);
	}
	// 核心过程
	int f = 0, e = 0;
	stack<char> st;
	for (int i = 0; i < a.size(); i++) {
		s = a[i];
		// 如果程序不是E
		if (s.size() > 3) {
			// 并且变量名字已经用过了
			if (vis[s[2]]) {
				cout << "ERR\n";
				return;
			}
			// 否则，标记一下，压入栈里面
			vis[s[2]] = 1;
			st.push(s[2]); // 压入栈
		}
		// 统计F和E的数量，因为F和E可以一对消除
		if (s[0] == 'F') f++;
		if (s[0] == 'E') {
			e++;
			if (!st.empty()) { // 销毁变量名
				char top = st.top();
				vis[top] = 0;
				st.pop();
			}
		}
	}
	if (f != e) { // F和E不匹配
		cout << "ERR\n";
		return;
	}

	long long sum = 0, mi = 0;
	bool flag = false;
	for (int i = 0; i < a.size(); i++) {
		s = a[i];
		// 提取循环中的x和y，由于x和y不一定为1位数，故需要切片提取
		if (s.size() != 1) {
			int pos = s.find(' ', 4);
			string x = s.substr(4, pos - 4);
			string y = s.substr(pos + 1);
			// x和y都是数字的情况
			if (x.find('n') == -1 && y.find('n') == -1) {
				if (atoi(x.c_str()) > atoi(y.c_str())) flag = 1;
			}
			// x为n，y为数字的情况
			else if (x == "n" && y != "n") flag = 1;
			// x为数字，y为n的情况。
			else if (y == "n" && x != "n") {  // 这层循环有可能会执行，因为有可能上层循环已经pass掉了，这层即便没错误也不能执行。
				if (!flag) mi++;
			}
			// 更新幂数
			sum = max(sum, mi);
		}
		// 碰到E的情况
		else {
			mi--;
			if (mi < 0)mi = 0;
			flag = 0; // 重置
		}  
	}
	// 常数的时间复杂度的情况
	if (sum == 0) {
		if (o == "O(1)") cout << "Yes\n";
		else cout << "No\n";
	}
	else {
		// 通过字符串的切片判断计算的幂数是否和给的幂数一致
		int cur = o.find(')');
		string a = o.substr(4, cur - 4);
		if (sum == stoi(a)) cout << "Yes\n";
		else cout << "No\n";
	}

}


int main() {
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

运行结果