前情提要
夏令营教模拟，老师给了我们这个作业。我当时特喜欢刷水题。当时，我觉得这道题很水，轻松搞定，于是直奔满分而去。结果......也就调了亿会。
为了弥补这一个月之劳累，特写此题解。
铺垫
（注：这里我用字符串存储小明认为的复杂度。）
定义该循环“对复杂度有贡献”当且仅当循环下界与上界之差远大于 \(100\)。这种循环是我们要统计的。
定义“废循环”为不对复杂度的次数有贡献的循环。这种循环是需要避免计算入复杂度的。
处理语法错误的方法
一个程序语法错误当且仅当：（括号内为解决方案）
- 变量重名；（用 \(arr\) 数组记录变量是否被使用）
F与E不对应。（用栈模拟循环）
正片
本题解着重讲解模拟思路，想倒不难。
处理复杂度步骤描述
首先：读入每行程序的第一个字符。
是 F：处理此循环的标记
- 读入变量名、循环下界和上界。
- 如果和 \(arr\) 数组之前记录的变量名重名：
- 标记语法错误，重新读入，忽略该组程序。（避免重复输出）
- 否则：
- 在 \(arr\) 数组中标记变量名，并将变量名压入循环栈中；（方便销毁变量名）
- 将
n赋值为一个极大值；（方便计算复杂度） - 如果这个循环没有被标记为废循环，且循环对复杂度有贡献：
- 将该循环标记为有贡献的；
- 当前次数 \(w\to w+1\)；
- 更新最大次数 \(res\)。
- 否则：
- 标记该变量名下的循环为废循环。
if(a == 'F'){cin >> b >> c >> d;if(arr[b - 'a'] && !ERR){cout << "ERR\n";ERR = 1; continue; //变量名重复} else {arr[b - 'a'] = 1;st.push(b); if(c == "n"){ c = "20000";}if(d == "n"){ d = "20000";}int C = stoi(c), D = stoi(d);if(D-C > 1000 && flag == -1){eff[b - 'a'] = 1; ++w;res = max(w, res);//判定复杂度} else if(C > D){flag = b; //废循环}}
}
是 E：撤销之前对与之对应的循环的标记
- 如果这个栈是空的：
- 标记语法错误，重新读入，忽略该组程序。
- 否则：
- 取出栈顶的变量名；
- 从栈中弹出这个循环；
- 撤销变量名重名标记；
- 如果该变量名下的循环为废循环：
- 撤销废循环标记。
- 否则，如果该变量名下的循环对复杂度有贡献：
- 撤销贡献标记，当前次数 \(w\to w-1\)。
else {if(st.empty()){if(! ERR){cout << "ERR\n"; ERR = 1;} continue;} int cur = st.top();st.pop();arr[cur - 'a'] = 0;if(flag == cur) { flag = -1; }if(eff[cur - 'a']) {eff[cur - 'a'] = 0;w --;}
}
收尾，判定复杂度
- 如果栈中还有元素：
- 清空栈；
- 如果没有输出过
ERR：- 报告语法错误。
- 读入下一组数据。
- 特判
O(1)，即 \(\Theta(n^0)\)：- 如果语法正确且最终次数 \(res\) 为 \(0\)：
- 输出
Yes。
- 输出
- 否则：
- 输出
No。
- 输出
- 如果语法正确且最终次数 \(res\) 为 \(0\)：
- 否则截取复杂度的次数部分。\(^{[1]}\)（将截取的字符串转换为
int类型） - 如果次数部分等于 \(res\)：
- 输出
Yes；
- 输出
- 否则：
- 输出
No。
- 输出
\([1]\)：这类格式以 O(n^45) 为例。前 \(4\) 个字符为固定的，不为数字；最后一个字符为 )。所以，截取数字要从第 \(5\) 个字符开始（即 s[4]，4）到倒数第二个字符（s[s.size() - 1]，5），即可截取到 45。
if(st.size()){while(st.size()){st.pop();}if(!ERR) {cout << "ERR\n";}continue;
}
if(s == "O(1)" && !ERR){if(res == 0) {cout << "Yes\n";} else {cout << "No\n";}
} else if(!ERR) {string s1;for(int i=4; i<s.size()-1; ++i){s1 += s.substr(i, 1);}if(stoi(s1) == res) {cout << "Yes\n";} else {cout << "No\n";}
}
坑总结
- 多测必清空！
- 想好思路再写代码；
- 把语法错误的循环完全忽略。记录是否属于这类循环，并尽量在所有判断的条件加上
! ERR； - 特判循环下界和上界都是
n的情况； - 小明判定的复杂度中，次数可能不止一位。
总代码
模拟题最重要的是细节和思维。想到了思路，你完全可以敲出正解代码。此处建议自行编写。
#include <bits/stdc++.h>
using namespace std;
int _;
bool arr[30], eff[30];int main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);stack<int> st;cin >> _;while(_ --){int n, w=0, res=0, flag = -1, ERR = 0;string s, c, d;char a, b;memset(arr, 0, sizeof arr);memset(eff, 0, sizeof eff);cin >> n >> s;while(n --){cin >> a;if(a == 'F'){cin >> b >> c >> d;if(arr[b - 'a'] && !ERR){cout << "ERR\n";ERR = 1; continue; //变量名重复} else {arr[b - 'a'] = 1;st.push(b); if(c == "n"){ c = "20000";}if(d == "n"){ d = "20000";}int C = stoi(c), D = stoi(d);if(D-C > 1000 && flag == -1){eff[b - 'a'] = 1; ++w;res = max(w, res);//判定复杂度} else if(C > D){flag = b; //废循环}}} else {if(st.empty()){if(! ERR){cout << "ERR\n"; ERR = 1;} continue;} int cur = st.top();st.pop();arr[cur - 'a'] = 0;if(flag == cur) { flag = -1; }if(eff[cur - 'a']) {eff[cur - 'a'] = 0;w --;}}}if(st.size()){while(st.size()){st.pop();}if(!ERR) {cout << "ERR\n";}continue;}if(s == "O(1)" && !ERR){if(res == 0) {cout << "Yes\n";} else {cout << "No\n";}} else if(!ERR){string s1;for(int i=4; i<s.size()-1; ++i){s1 += s.substr(i, 1);}if(stoi(s1) == res) {cout << "Yes\n";} else {cout << "No\n";}}}return 0;
}