**链接 : ** Here!
**思路 : **
-
这是一道大模拟, 区分好情况就没问题了
-
循环构成部分 : $F , x , i , j$ 和 $E$ , 需要注意的是 $i , j$,
- 分析 $i, j$ 的情况 : - 当 $i, j$ 全为 $n$ 的时候, 复杂度为 $O(1)$ - 当 $i, j$ 为 $number$ 和 $n$ 的时候复杂度为 $O(n)$ - 当 $i, j$ 为 $n$ 和 $number$ 的时候复杂度为 $O(0)$ - 当 $i, j$ 全为 $number$ 时, 需要考虑 - 如果 $i > j$ 复杂度为 $O(0)$ - 否则复杂度为 $O(1)$ -
分析多个循环的复杂度情况 :
- 首先分析循环内外层嵌套的复杂度情况 :- | 外层复杂度 \ 内层复杂度 | O(0) | O(1) | O($n^{w_2}$) | | -------------- | ------------ | ------------ | ------------------------------------ | | O(0) | O(0) | O(0) | O(0) | | O(1) | O(1) | O(1) | O(n) | | O($n^{w_1}$) | O($n^{w_1}$) | O($n^{w_1}$) | multiply(O($n^{w_1}$), O($n^{w_2}$)) | - 然后**分析循环并列**的复杂度情况 : **选取并列复杂度较大的那个** -
错误情况 :
- $F$ 和 $E$ 不匹配
- 预期复杂度与实际复杂度不匹配 -
分析完成之后直接敲代码就$ok$了, 如果我们将整个大的循环嵌套并列的结构抽象成一棵树的话, 那就会发现, 必须存一下当前层的最大复杂度
代码 :
/*************************************************************************
> File Name: 时间复杂度.cpp
> Author:
> Mail:
> Created Time: 2017年11月22日 星期三 18时26分04秒
************************************************************************/
#include <cstdio>
#include <iostream>
#include <string>
#include <stack>
using namespace std;
struct expr {
char var; // 记录变量名
string st, ed; // 记录循环的开始终止位置
string tempO; // 记录复杂度
string nowLayerO; // 记录当前层的最大复杂度
};
int T, n;
string des; // 记录预测复杂度
int calNumber(const string &str) {
int temp = 0;
for (int i = 0 ; i < str.length() ; ++i) {
temp = temp * 10 + str[i] - '0';
}
return temp;
}
// 计算复杂度
void calComplexity(expr &exp) {
// case 1 : 如果st,ed全为n的话
if (exp.st == "n" && exp.ed == "n") {
exp.tempO = "1";
return;
}
// case 2 : 如果st为数字,ed为n
if (exp.st != "n" && exp.ed == "n") {
exp.tempO = "n";
return;
}
// case 3 : 如果st为n,ed为数字
if (exp.st == "n" && exp.ed != "n") {
exp.tempO = "0";
return;
}
// case 4 : 如果st,ed全为数字且st <= ed
// case 5 : 如果st,ed全为数字且st > ed
int st_num = calNumber(exp.st);
int ed_num = calNumber(exp.ed);
if (st_num <= ed_num) {
exp.tempO = "1";
} else {
exp.tempO = "0";
}
return;
}
// 计算str中的幂指数, str为n^w(w >= 1),当w为1的时候是可以省略的
int calExponent(const string &str) {
// 特殊情况
if (str == "n") {
return 1;
}
int ret = 0;
for (int i = 2 ; i < str.length() ; ++i) {
ret = ret * 10 + str[i] - '0';
}
return ret;
}
// 复杂度相乘
// 如果外层循环是O(0)那么a * b -> O(0)
// 如果内层循环是O(0)那么a * b -> a的复杂度
// a代表外层复杂度, b代表内层复杂度
string multiComplexity(const string &a, const string &b) {
string ret = "";
if (a == "0") {
ret = "0";
} else if (a == "1") {
if (b == "0") {
ret = "1";
} else {
ret = b;
}
} else {
if (b == "0") {
ret = a;
} else if (b == "1") {
ret = a;
} else {
// 如果能进入这里首先可以确定a,b为n^w
// 且a,b的w >= 1因此tstr直接写个前缀n^是完全没问题的
int expon1 = calExponent(a);
int expon2 = calExponent(b);
string tstr1 = "n^";
string tstr2 = "";
expon1 += expon2;
while (expon1) {
tstr2 += (char)((expon1 % 10) + '0');
expon1 /= 10;
}
for (int i = tstr2.length() - 1 ; i >= 0 ; --i) {
tstr1 += tstr2[i];
}
ret = tstr1;
}
}
return ret;
}
// 复杂度相加,选出复杂度较大的那个
string addComplexity(const string &a, const string &b) {
string ret = "";
if (a == "0") {
ret = b;
} else if (a == "1") {
ret = (b == "0" ? a : b);
} else {
if (b == "0" || b == "1") {
ret = a;
} else {
int expon1 = calExponent(a);
int expon2 = calExponent(b);
ret = (expon1 > expon2 ? a : b);
}
}
return ret;
}
void read() {
scanf("%d", &T);
while (T--) {
int vis[30] = {0}, flag = 0; // 标记是否出现变量名冲突
cin >> n >> des;
expr exp[n];
stack<expr> myStack;
string sum = "0";
string maxO = "0";
for (int i = 0 ; i < n ; ++i) {
char firstCh;
cin >> firstCh;
if (firstCh != 'E') {
cin >> exp[i].var >> exp[i].st >> exp[i].ed;
if (vis[exp[i].var - 'a']) {
flag = 1;
}
vis[exp[i].var - 'a'] = 1;
calComplexity(exp[i]);
// cout << "exp.tempO : " << exp[i].tempO << endl;
exp[i].nowLayerO = exp[i].tempO;
myStack.push(exp[i]);
} else {
// 如果遇到E则该弹栈计算了
// 并且更新新栈顶当前层数最大复杂度
// 如果空栈还弹,那说明ERR
if (myStack.empty()) {
flag = 1;
continue;
}
expr topExp = myStack.top();
myStack.pop();
vis[topExp.var - 'a'] = 0;
// 先获取当弹出的当前层最大复杂度
string temp1 = topExp.nowLayerO;
// 暂存一下当前最大复杂度
maxO = topExp.nowLayerO;
// 如果能向上更新这个最大复杂度
if (!myStack.empty()) {
topExp = myStack.top();
myStack.pop();
topExp.nowLayerO = addComplexity(topExp.nowLayerO, multiComplexity(topExp.tempO, temp1));
myStack.push(topExp);
}
// cout << " maxO : " << maxO << endl;
}
// 如果栈为空,那么说一个loop已经结束了
if (myStack.empty()) {
sum = addComplexity(sum, maxO);
maxO = "0";
}
}
if (flag || !myStack.empty() || (n & 1)) {
printf("ERR
");
} else {
// cout << "ans : " << sum << endl;
if (sum == "n") sum = "n^1";
if (sum == "0") sum = "1";
sum = "O(" + sum + ")";
if (sum == des) {
printf("Yes
");
} else {
printf("No
");
}
}
}
}
int main() {
read();
return 0;
}