[Luogu 3952] NOIP2017 时间复杂度
一年的时间说长不长，说短，也不短。
一年之内无数次觉得难得可怕的题目，原来也就模拟这么回事儿。
#include <cstdio>
#include <iostream>
#include <set>
#include <stack>
#include <string>
int T;
struct Layer
{
std::string name;
int state;
Layer(std::string name, int state): name(name), state(state){}
};
int Solve(std::string s)
{
if(s == "O(1)")
return 0;
int ans = 0;
for(int i = 4; s[i] != ')'; ++i)
ans = ans * 10 + s[i] - '0';
return ans;
}
int Number(std::string s)
{
if(s[0] == 'n')
return 0;
int ans = 0;
for(int i = 0; s[i]; ++i)
ans = ans * 10 + s[i] - '0';
return ans;
}
int main(void)
{
scanf("%d", &T);
while(T--)
{
bool right = true;
int n, ans, cur = 0, fact = 0;
std::set<std::string> Name;
std::stack<Layer> S;
std::string a[5];
scanf("%d", &n);
std::cin >> a[0];
ans = Solve(a[0]);
for(int i = 1; i <= n; ++i)
{
std::cin >> a[1];
if(a[1] == "F")
{
for(int i = 2; i <= 4; ++i)
std::cin >> a[i];
if(right && !Name.count(a[2]))
{
int state, x = Number(a[3]), y = Number(a[4]);
if((!S.empty() && S.top().state == -1) || (!x && y) || (x > y && y))
state = -1;
else if(x && !y)
{
state = 1;
++cur;
}
else
state = 0;
Name.insert(a[2]);
S.push(Layer(a[2], state));
}
else
right = false;
}
else if(right)
{
if(!S.empty())
{
Layer t = S.top();
Name.erase(t.name);
S.pop();
fact = std::max(fact, cur);
if(t.state == 1)
--cur;
}
else
right = false;
}
}
if(!S.empty())
right = false;
if(!right)
puts("ERR");
else
puts(ans == fact ? "Yes" : "No");
}
return 0;
}
谢谢阅读。