毒瘤大模拟题！
看到这种又是字符串又是模拟的题目就很伤，很多的地方都考验细节。
看到这种处理循环的方式是后进先出，自然想到了用栈来模拟。
但是最主要的思路是怎么算复杂度？
其实说白了也简单：一个循环的复杂度 = 这个循环本身的复杂度 + 在里面嵌套的最大的复杂度
这里的每一个循环变量都是不重复的，如果重复直接判ERR。
那么我们就可以用一个循环变量来代表一个循环，利用他们记录一个循环本身的复杂度和实际的复杂度。
如何计算一个循环的本身时间复杂度？
如果x不是\(n\)，y是\(n\)，这个循环是\(O(n)\)的。
如果x和y都是\(n\)，这个循环是\(O(1)\)的。
如果x是\(n\)而y不是\(n\)，那么这个循环不执行。
如果x和y都是数字，比较他们的大小，当且仅当\(x \leq y\)时有\(O(1)\)的复杂度，否则不执行。
这里有一个很重要的思想：如果一个循环不执行，那么我就不去考虑这个循环内的任何时间复杂度！顶多看看会不会有语法错误就好了。
而有一个挺特殊的情况：如果任何循环都不执行的话是\(O(1)\)的。这个在样例已经跟你说了。
维护的时候直接用一个数字来维护，意义是\(n\)的几次方，所以\(O(1)\)用0来代替，不执行的情况我用-1来搞。
ERR总共有3种情况：
F太多。这个在最后看看栈是不是空的就可以了。
E太多。那么这个时候会发生栈下溢，特判解决。
变量重名。开一个used数组判一下就可以了。
总体来说不难，但是需要你有正确的思路！！！
这个故事告诉我们：写大模拟的时候一定要先想清楚所有的情况再写！
说人话就是：
\[\huge{Think \quad twice, code \quad once!}\]
代码：
#include#include #include #include #include #include using namespace std;string str[105];bool used[30];int source[30], comp[30];int id(char x){ return x - 'a' + 1;}int to_int(string x){ int len = x.length(), ans = 0; for(int i = 0; i < len; i++) ans = ans * 10 + x[i] - '0'; return ans;}int calc(string x, string y){ bool flag1 = (x[0] != 'n'), flag2 = (y[0] != 'n');// is a number if(flag1) { if(flag2) { int num1 = to_int(x), num_2 = to_int(y); if(num1 <= num_2) return 0; else return -1; } else return 1; } else { if(flag2) return -1; else return 0; }}int solve(int len, int expected){ memset(used, false, sizeof used); memset(source, 0, sizeof source); memset(comp, 0, sizeof comp); stack sta; int ans = 0; for(int i = 1; i <= len; i++) { stringstream ss(str[i]); string opt, name, x, y; ss >> opt; if(opt[0] == 'F') { ss >> name >> x >> y; if(used[id(name[0])]) return 3;// ERR used[id(name[0])] = true; comp[id(name[0])] = source[id(name[0])] = calc(x, y); sta.push(name[0]); } else if(opt[0] == 'E') { if(sta.empty()) return 3;// ERR char name = sta.top(); sta.pop(); used[id(name)] = false; if(sta.empty()) { ans = std::max(ans, comp[id(name)]); } else { if(source[id(sta.top())] != -1) comp[id(sta.top())] = std::max(comp[id(sta.top())], source[id(sta.top())] + comp[id(name)]); } } } if(!sta.empty()) return 3;// ERR if(ans == expected) return 1; else return 2;}void print(int res){ if(res == 1) cout << "Yes\n"; else if(res == 2) cout << "No\n"; else if(res == 3) cout << "ERR\n"; else cout << "I AK NOIP!\n";}int main(){ int T; cin >> T; while(T--) { int len, expected; string temp; cin >> len >> temp; if(temp[2] == '1') expected = 0; else { stringstream ss(temp.substr(4)); ss >> expected; } for(int i = 0; i <= len; i++) getline(cin, str[i]); int res = solve(len, expected); print(res); } return 0;}