算法知识点: 栈，模拟，字符串处理
复杂度：)
解题思路：
循环的时间复杂度取决于最内层的计算次数，即嵌套最深的一层循环的计算次数。
循环的嵌套和括号序列的嵌套类似，所以我们可以借助栈来遍历整个代码序列。
当遇到FOR语句时，将该循环压入栈顶，当遇到END语句时，将栈顶的循环弹出。那么栈中从底到顶的序列就是当前循环从外到内嵌套的序列。
对于每层循环FOR i x y，我们先判断它的计算次数cmp：
x 是 n 时:
y 也是 n，那么循环次数是 O(1);
y 是正整数，由于 n 远大于100，且 x,y 在100以内，所以这个循环一次也不执行；
x 是正整数时：
y 是 n,那么会循环 O(n) 次；
y 是正整数，如果 x≤y，那么会循环 O(1)次，如果 x>y，那么一次也不执行；
然后判断整个循环嵌套序列的计算次数：
如果外层循环中的某一层执行次数是0或者当前循环的执行次数是0，那么当前这层的计算次数就是0；
否则当前这层的循环次数就是上一层循环的执行次数乘以前面判断出的循环次数 cmp；
语法错误有两种：
对于当前循环创建的变量，如果在栈中已经出现过，说明与外面的某一层循环的循环变量重名了，产生语法错误；
如果遍历过程中对空栈执行弹出操作，或者遍历结束后栈不为空，说明FOR语句与END语句不匹配，产生语法错误。
时
时间复杂度分析:
总共有 T 个测试数据，对于每个测试数据，每个循环会进栈一次，出栈一次，每次进栈之前会循环一遍栈中所有元素，判断是否存在变量重名的情况，所以总时间复杂度是。
C++ 代码
#include <iostream>
#include <algorithm>
#include <sstream>
using namespace std;
typedef pair <char, int> PCI; const int N = 110;
int tt;
PCI stk[N]; // 栈中存储当前嵌套的所有循环
// first存储每一层的变量名
// second存储到当前这层总共的计算量，如果为-1，表示当前这层无法到达
int get_number(string str) // 将字符串转化成整数
{
int res = 0;
for (auto c: str) res = res * 10 + c - '0';
return res;
}
int get_time(string str) // 提取出str中n的次数
{
if (str == "O(1)") return 0;
int t = str.find('^');
string num = str.substr(t + 1);
num.pop_back();
return get_number(num);
}
bool has(char c) // 判断当前栈中是否已经存在变量c
{
for (int i = 1; i <= tt; i++)
if (stk[i].first == c)
return true;
return false;
}
int get_cmp(string x, string y) // 判断 for (int i = x; i <= y; i ++) 的循环次数是n的多少次方
{
if (x == "n")
{
if (y == "n") return 0;
return -1;
}
if (y == "n") return 1;
int a = get_number(x), b = get_number(y);
if (a <= b) return 0;
return -1;
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int n;
string str;
cin >> n >> str;
int tm = get_time(str);
int max_cmp = 0;
bool error = false;
tt = 0;
string line;
getline(cin, line);
for (int i = 0; i < n; i++)
{
getline(cin, line);
if (!error)
{
if (line == "E")
{
if (tt) tt--;
else error = true;
}
else
{
stringstream sin(line);
string F, i, x, y;
sin >> F >> i >> x >> y;
if (has(i[0])) error = true;
else
{
int cmp = get_cmp(x, y);
if (!tt) stk[++tt] = {
i[0], cmp
};
else
{
int computation = -1; // -1表示当前这层无法到达
if (stk[tt].second >= 0 && cmp >= 0) computation = stk[tt].second + cmp;
stk[++tt] = {
i[0], computation
};
}
max_cmp = max(max_cmp, stk[tt].second);
}
}
}
}
if (tt) error = true;
if (error) puts("ERR");
else if (tm == max_cmp) puts("Yes");
else puts("No");
}
return 0;
} 
京公网安备 11010502036488号