时间复杂度
···
include [HTML_REMOVED]
include [HTML_REMOVED]
include [HTML_REMOVED]
using namespace std;
typedef pair[HTML_REMOVED] PCI;
const int N = 110;
int tt;
PCI stk[N];
int get_number(string number)
{
int res = 0;
for (int i = 0; i < number.size(); i ++ ) res = res * 10 + number[i] - ‘0’;
return res;
}
int get_time(string str)
{
if (str == “O(1)”) return 0;
int t = str.find(‘^’);
string number = str.substr(t + 1);
number.pop_back();
return get_number(number);
}
bool have(char c)
{
for (int i = 1; i <= tt; i ++ )
if (stk[i].first == c)
return true;
return false;
}
int get_for_time(string x, string y)
{
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 -1;
return 0;
}
int main()
{
int T;
cin >> T;
while (T – )
{
int n;
string str;
cin >> n >> str;
int O = get_time(str);
getline(cin, str);
tt = 0;
int max_time = 0;
bool error = false;
while (n -- )
{
getline(cin, str);
if (error) continue;
if (str == "E")
{
if (tt) tt -- ;
else error = true;
}
else
{
stringstream sin(str);
string F, i, x, y;
sin >> F >> i >> x >> y;
if (have(i[0])) error = true;
else
{
int tm = get_for_time(x, y);
if (tm >= 0 && stk[tt].second >= 0) tm += stk[tt].second;
else tm = -1;
stk[ ++ tt] = make_pair(i[0], tm);
max_time = max(max_time, tm);
}
}
}
if (tt) error = true;
if (error) puts("ERR");
else if (max_time == O) puts("Yes");
else puts("No");
}
return 0;
}
···