洛谷P3952 时间复杂度
程序员文章站
2024-03-19 09:25:40
...
非常繁琐,细节巨多。
1.尤其注意两个n出现时按常数算。
2.读入数字时要读整个字符串,而不是单个字符
#include<cstring>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<iostream>
using namespace std;
const int inf = 100000 + 3;
int check[200];
inline int get(char a){ return (int)a; }
inline int exchange(char h[])
{
if(h[0] == 'n')return inf;
else
{
int num = 0, cnt = 0;
while(h[cnt] >= '0' && h[cnt] <= '9')
{
num = num * 10 + h[cnt] - '0';
++cnt;
}
return num;
}
}
struct Node
{
int skip, comp, idx;
Node(int skip = 0,int comp = 0,int idx = 0):skip(skip), comp(comp), idx(idx){}
};
stack<Node>S;
int main()
{
//freopen("f.txt","r",stdin);
int T;
scanf("%d",&T);
char h[10];
char s[20];
while(T--)
{
while(!S.empty()) S.pop();
memset(check,0,sizeof(check));
int n;
int flag = 1, ans = 0;
scanf("%d",&n);
scanf("%s",s);
for(int i = 1;i <= n;++i)
{
scanf("%s",h);
if(h[0] == 'E')
{
if(S.empty()) {flag = 0;}
else
{
Node u = S.top();
check[u.idx] = 0;
ans = max(ans,u.comp);
S.pop();
}
continue;
}
Node new_node;
scanf("%s",h);
int id = get(h[0]), num1, num2, cm = 0;
if(check[id]) {flag = 0;}
check[id] = 1;
scanf("%s",h); num1 = exchange(h);
scanf("%s",h); num2 = exchange(h);
cm = (!S.empty()) ? S.top().comp : 0;
// printf("%d %d\n",num1,num2);
if(num1 > num2) S.push(Node(1,0,id));
else
{
if(!S.empty() && S.top().skip == 1)S.push(Node(1,0,id));
else
{
if(num2 == inf && num1 != inf) ++cm;
ans = max(ans,cm);
S.push(Node(0,cm,id));
}
}
}
if(flag == 0 || !S.empty()) printf("ERR\n");
else
{
if(s[2] - '0' == 1)
{
if(ans == 0) printf("Yes\n");
else printf("No\n");
}
else
{
int num = 0, cnt = 4;
while(s[cnt] >= '0' && s[cnt] <= '9')
{
num = num * 10 + s[cnt] - '0';
++cnt;
}
if(num == ans) printf("Yes\n");
else printf("No\n");
}
}
}
return 0;
}
上一篇: Strange Optimization
下一篇: C++难点记录