P8289 的第 5 个测试点和第 10 个测试点 MLE 了,但是我在洛谷 IDE 运行只占用了 564 kb。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int n;
string s, k;
map<string, string> p, tmp;
map<string, bool> f, ft;
string solve(string s, bool flag) {
if (s == k && flag) return s;
if (ft[s]) return tmp[s];
string name, res;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') name.push_back(s[i]);
else if (s[i] >= 'a' && s[i] <= 'z') name.push_back(s[i]);
else if (s[i] >= 'A' && s[i] <= 'Z') name.push_back(s[i]);
else if (s[i] == '_') name.push_back(s[i]);
else {
if (f[name] && !ft[name]) tmp[name] = solve(p[name], 1), ft[name] = 1, res = res + tmp[name];
else if (f[name]) res = res + tmp[name];
else res = res + name;
name = "";
res = res + s[i];
}
}
if (f[name] && !ft[name]) tmp[name] = solve(p[name], 1), ft[name] = 1, res = res + tmp[name];
else if (f[name]) res = res + tmp[name];
else res = res + name;
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
getline(cin, s);
for (int i = 1; i <= n; i++) {
getline(cin, s);
if (s[0] == '#') {
tmp.clear(), ft.clear();
if (s[1] == 'd') {
string name, content;
int j = 8;
while (j < s.size() && s[j] != ' ') j++;
name = s.substr(8, j - 8), content = s.substr(j + 1, s.size() - j);
p[name] = content;
f[name] = 1;
}
else {
string name = s.substr(7, s.size() - 7);
p[name] = "";
f[name] = 0;
}
}
else {
string name;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') name.push_back(s[i]);
else if (s[i] >= 'a' && s[i] <= 'z') name.push_back(s[i]);
else if (s[i] >= 'A' && s[i] <= 'Z') name.push_back(s[i]);
else if (s[i] == '_') name.push_back(s[i]);
else {
k = p[name];
if (f[name] && !ft[name]) tmp[name] = solve(p[name], 0), ft[name] = 1, cout << tmp[name];
else if (f[name]) cout << tmp[name];
else cout << name;
name = "";
cout << s[i];
}
}
k = p[name];
if (f[name] && !ft[name]) tmp[name] = solve(p[name], 0), ft[name] = 1, cout << tmp[name];
else if (f[name]) cout << tmp[name];
else cout << name;
}
cout << endl;
}
return 0;
}
我发现是 solve 导致 MLE 了,但是我输出了 solve 的调用次数,总共只调用了 33 次。